Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1160184 > unrolled thread

Re: [PATCH 08/14] hrtimer: Allow hrtimer::function() to free the timer

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 08/14] hrtimer: Allow hrtimer::function() to free the  timer Oleg Nesterov <oleg@redhat.com> - 2015-06-08 00:40 +0200
    Re: [PATCH 08/14] hrtimer: Allow hrtimer::function() to free the  timer Oleg Nesterov <oleg@redhat.com> - 2015-06-08 01:00 +0200
    Re: [PATCH 08/14] hrtimer: Allow hrtimer::function() to free the  timer Peter Zijlstra <peterz@infradead.org> - 2015-06-08 13:00 +0200
    Re: [PATCH 0/3] hrtimer: HRTIMER_STATE_ fixes Peter Zijlstra <peterz@infradead.org> - 2015-06-08 21:10 +0200
    Re: [PATCH 08/14] hrtimer: Allow hrtimer::function() to free the  timer Peter Zijlstra <peterz@infradead.org> - 2015-06-11 00:40 +0200

#1160184 — Re: [PATCH 08/14] hrtimer: Allow hrtimer::function() to free the timer

Not sure I read this patch correctly, it doesn't apply to Linus's tree.

And I simply can not understand the complication in hrtimer_active(),
please help!

On 06/05, Peter Zijlstra wrote:
>
> +bool hrtimer_active(const struct hrtimer *timer)
> +{
> +	struct hrtimer_cpu_base *cpu_base;
> +	unsigned int seq;
> +	bool active;
> +
> +	do {
> +		active = false;
> +		cpu_base = READ_ONCE(timer->base->cpu_base);
> +		seq = raw_read_seqcount(&cpu_base->seq);
> +
> +		if (timer->state != HRTIMER_STATE_INACTIVE ||
> +		    cpu_base->running == timer)
> +			active = true;

Why we can't simply return true in this case?

Unless you lock this timer, hrtimer_active() is inherently racy anyway.
Granted, it must not wrongly return False if the timer is pending or
running.

But "false positive" does not differ from the case when (say) the
running timer->function() finishes right after hrtimer_active() returns
True.

> +	} while (read_seqcount_retry(&cpu_base->seq, seq) ||
> +		 cpu_base != READ_ONCE(timer->base->cpu_base));

Why do we need to re-check >cpu_base?

I think we can ignore migrate_hrtimer_list(), it doesn't clear ->state.

Otherwise the timer can change its ->base only if it is not running and
inactive, and again I think we should only eliminate the false negative
return.

And I think there is a problem. Consider a timer TIMER which always
rearms itself using some "default" timeout.

In this case __hrtimer_start_range_ns(&TIMER, ...) must preserve
hrtimer_active(&TIMER) == T. By definition, and currently this is
true.

After this patch this is no longer true (afaics). If the timer is
pending but not running, __hrtimer_start_range_ns()->remove_hrtimer()
will clear ENQUEUED first, then set it again in enqueue_hrtimer().

This means that hrtimer_active() returns false in between. And note
that it doesn't matter if the timer changes its ->base or not, so
that 2nd cpu_base above can't help.

I think that __hrtimer_start_range_ns() should preserve ENQUEUED
like migrate_hrtimer_list() should do (see the previous email).


Finally. Suppose that timer->function() returns HRTIMER_RESTART
and hrtimer_active() is called right after __run_hrtimer() sets
cpu_base->running = NULL. I can't understand why hrtimer_active()
can't miss ENQUEUED in this case. We have wmb() in between, yes,
but then hrtimer_active() should do something like

	active = cpu_base->running == timer;
	if (!active) {
		rmb();
		active = state != HRTIMER_STATE_INACTIVE;
	}

No?

But I am already sleeping and probably totally confused.

Oleg.

--
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/

[toc] | [next] | [standalone]

#1160185

On 06/08, Oleg Nesterov wrote:
>
> And I simply can not understand the complication in hrtimer_active(),
> please help!

Sorry for another off-topic email, but I don't even understand the
usage of hrtimer_active().

Say, do_nanosleep()

		hrtimer_start_expires(&t->timer, mode);
		if (!hrtimer_active(&t->timer))
			t->task = NULL;

why? Assuming that hrtimer_active() is correct, it can only return
false if t->task was already cleared by hrtimer_wakeup().


OTOH. perf_cpu_hrtimer_restart() does

	if (hrtimer_active(hr))
		return;

	if (!hrtimer_callback_running(hr))
		__hrtimer_start_range_ns(...);

why it can't simply do

	if (!hrtimer_active(hr)) // implies !hrtimer_callback_running()
		__hrtimer_start_range_ns(...);


Confused.

Oleg.

--
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/

[toc] | [prev] | [next] | [standalone]

#1160405

On Mon, Jun 08, 2015 at 11:14:17AM +0200, Peter Zijlstra wrote:
> On Mon, Jun 08, 2015 at 12:33:17AM +0200, Oleg Nesterov wrote:
> > Not sure I read this patch correctly, it doesn't apply to Linus's tree.
> 
> I was working on tip/master, there's a number of timer patches in there.
> 
> > And I simply can not understand the complication in hrtimer_active(),
> > please help!
> > 
> > On 06/05, Peter Zijlstra wrote:
> > >
> > > +bool hrtimer_active(const struct hrtimer *timer)
> > > +{
> > > +	struct hrtimer_cpu_base *cpu_base;
> > > +	unsigned int seq;
> > > +	bool active;
> > > +
> > > +	do {
> > > +		active = false;
> > > +		cpu_base = READ_ONCE(timer->base->cpu_base);
> > > +		seq = raw_read_seqcount(&cpu_base->seq);
> > > +
> > > +		if (timer->state != HRTIMER_STATE_INACTIVE ||
> > > +		    cpu_base->running == timer)
> > > +			active = true;
> > 
> > Why we can't simply return true in this case?
> > 
> > Unless you lock this timer, hrtimer_active() is inherently racy anyway.
> > Granted, it must not wrongly return False if the timer is pending or
> > running.
> > 
> > But "false positive" does not differ from the case when (say) the
> > running timer->function() finishes right after hrtimer_active() returns
> > True.

OK I can't read; you asked why delay the return true inside that loop.

Yes we can as per your argument. I think I ended up being too paranoid
or something.
--
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/

[toc] | [prev] | [next] | [standalone]

#1160720 — Re: [PATCH 0/3] hrtimer: HRTIMER_STATE_ fixes

On Mon, 2015-06-08 at 19:11 +0200, Thomas Gleixner wrote:

> > Ah, yes, we could introduce timerqueue_is_queued() which uses
> > RB_EMPTY_NODE(). Obviating the need for hrtimer::state entirely.
> 
> Which won't work for the migration case unless we have some trickery
> like we do with double linked lists (not setting the prev member to
> NULL on dequeue).

Yeah, that dawned on me while away from the computer.

--
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/

[toc] | [prev] | [next] | [standalone]

#1162920

On Tue, Jun 09, 2015 at 11:33:18PM +0200, Oleg Nesterov wrote:

> And. Note that we can rewrite these 2 "write" critical sections in
> __run_hrtimer() and enqueue_hrtimer() as
> 
> 	cpu_base->running = timer;
> 
> 	write_seqcount_begin(cpu_base->seq);
> 	write_seqcount_end(cpu_base->seq);
> 
> 	__remove_hrtimer(timer);
> 
> and
> 
> 	timer->state |= HRTIMER_STATE_ENQUEUED;
> 
> 	write_seqcount_begin(cpu_base->seq);
> 	write_seqcount_end(cpu_base->seq);
> 
> 	base->running = NULL;
> 
> So we can probably use write_seqcount_barrier() except I am not sure
> about the 2nd wmb...

Which second wmb?

In any case, you use that transform from your reply to Kirill, and I
cannot currently see a hole in that. Lets call this transformation A. It
gets us the quoted bit above.

Now the above is:

	seq++;
	smp_wmb();
	smp_wmb();
	seq++;

Now, double barriers are pointless, so I think we can all agree that the
above is identical to the below. Lets call this tranformation B.

	seq++;
	smp_wmb();
	seq++;

And then because you use the traditional seqcount read side, which
stalls when seq&1, we can transform the above into this. Transformation
C.

	smp_wmb();
	seq += 2;

Which is write_seqcount_barrier(), as you say above.

And since there are no odd numbers possible in that scheme, its
identical to my modified read side with the single increment. Transform
D.

The only difference at this point is that I have my seq increment on the
'wrong' side on the first state.

	cpu_base->running = timer;

	seq++;
	smp_wmb();

	timer->state = 0;

	...

	timer->state = 1;

	smp_wmb();
	seq++;

	cpu_base->running = NULL;

Which, per my previous mail provides the following:

[S] seq++
                                [R] seq
                                    RMB
                                [R] ->running (== NULL)
[S] ->running = timer;
    WMB
[S] ->state = INACTIVE
                                [R] ->state (== INACTIVE)
                                    RMB
                                [R] seq (== seq)

Which is where we had to modify the read side to do:

		[R] ->state
		    RMB
		[R] ->running

Now, if we use write_seqcount_barrier() that would become:

	__run_hrtimer()				hrtimer_active()

	[S] ->running = timer;			[R] seq
	    WMB					    RMB
	[S] seq += 2;				[R] ->running
	[S] ->state = 0;			[R] ->state
						    RMB
						[R] seq


Which we can reorder like:

						[R] seq
						    RMB
						[R] ->running (== NULL)
	[S] ->running = timer
	    WMB
	[S] ->state = 0
						[R] ->state (== 0)
						   RMB
						[R] seq (== seq)
	[S] seq += 2


Which still gives us that false negative and would still require the
read side to be modified to do:

		[R] ->state
		    RMB
		[R] ->running

IOW, one of our transforms (A-D) is faulty for it requires a
modification to the read side.

I suspect its T-C, where we loose the odd count that holds up the read
side.

Because the moment we go from:

	Y = true;
	seq++
	WMB
	seq++
	X = false;

to:

	Y = true;
	WMB
	seq += 2;
	X = false;

It becomes possible to re-order like:

	Y = true;
	WMB
	X = false

	seq += 2;

And we loose our read order; or rather, where previously we ordered the
read side by seq, the seq increments are no longer ordered.

With this I think we can prove my code correct, however it also suggests
that:

	cpu_base->running = timer;
	seq++;
	smp_wmb();
	seq++;
	timer->state = 0;

	...

	timer->state = 1;
	seq++;
	smp_wmb();
	seq++;
	cpu_base->running = NULL;

vs
	hrtimer_active(timer)
        {

                do {
                        base = READ_ONCE(timer->base->cpu_base);
                        seq = read_seqcount_begin(&cpu_base->seq);

                        if (timer->state & ENQUEUED ||
                            base->running == timer)
                                return true;

                } while (read_seqcount_retry(&cpu_base->seq, seq) ||
                         base != READ_ONCE(timer->base->cpu_base));

                return false;
        }

Is the all-round cheapest solution. Those extra seq increments are
almost free on all archs as the cacheline will be hot and modified on
the local cpu.

Only under the very rare condition of a concurrent hrtimer_active() call
will that seq line be pulled into shared state.


I shall go sleep now, and update my patch tomorrow, lets see if I will
still agree with myself after a sleep :-)
--
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/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web