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

Groups > linux.kernel > #1460748 > unrolled thread

Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention

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: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention Dave Hansen <dave.hansen@intel.com> - 2016-08-11 21:40 +0200
    Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention Dave Hansen <dave.hansen@intel.com> - 2016-08-12 02:40 +0200
      Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention Dave Hansen <dave.hansen@intel.com> - 2016-08-12 19:20 +0200
        Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention Andy Lutomirski <luto@amacapital.net> - 2016-08-12 22:20 +0200
          Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention Dave Hansen <dave.hansen@intel.com> - 2016-08-12 23:20 +0200
          Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention Dave Hansen <dave.hansen@intel.com> - 2016-08-12 23:30 +0200

#1460748 — Re: [RESEND PATCH v4] x86/hpet: Reduce HPET counter read contention

On 08/10/2016 11:29 AM, Waiman Long wrote:
> +static cycle_t read_hpet(struct clocksource *cs)
> +{
> +	int seq;
> +
> +	seq = READ_ONCE(hpet_save.seq);
> +	if (!HPET_SEQ_LOCKED(seq)) {
...
> +	}
> +
> +	/*
> +	 * Wait until the locked sequence number changes which indicates
> +	 * that the saved HPET value is up-to-date.
> +	 */
> +	while (READ_ONCE(hpet_save.seq) == seq) {
> +		/*
> +		 * Since reading the HPET is much slower than a single
> +		 * cpu_relax() instruction, we use two here in an attempt
> +		 * to reduce the amount of cacheline contention in the
> +		 * hpet_save.seq cacheline.
> +		 */
> +		cpu_relax();
> +		cpu_relax();
> +	}
> +
> +	return (cycle_t)READ_ONCE(hpet_save.hpet);
> +}

It's a real bummer that this all has to be open-coded.  I have to wonder
if there were any alternatives that you tried that were simpler.

Is READ_ONCE()/smp_store_release() really strong enough here?  It
guarantees ordering, but you need ordering *and* a guarantee that your
write is visible to the reader.  Don't you need actual barriers for
that?  Otherwise, you might be seeing a stale HPET value, and the spin
loop that you did waiting for it to be up-to-date was worthless.  The
seqlock code, uses barriers, btw.

Also, since you're fundamentally reading a second-hand HPET value, does
that have any impact on the precision of the HPET as a timesource?  Or,
is it so coarse already that this isn't an issue?

[toc] | [next] | [standalone]

#1460879

On 08/11/2016 04:22 PM, Waiman Long wrote:
> On 08/11/2016 03:32 PM, Dave Hansen wrote:
>> It's a real bummer that this all has to be open-coded.  I have to wonder
>> if there were any alternatives that you tried that were simpler.
> 
> What do you mean by "open-coded"? Do you mean the function can be inlined?

I just mean that it's implementing its own locking instead of being able
to use spinlocks or seqlocks, or some other existing primitive.

>> Is READ_ONCE()/smp_store_release() really strong enough here?  It
>> guarantees ordering, but you need ordering *and* a guarantee that your
>> write is visible to the reader.  Don't you need actual barriers for
>> that?  Otherwise, you might be seeing a stale HPET value, and the spin
>> loop that you did waiting for it to be up-to-date was worthless.  The
>> seqlock code, uses barriers, btw.
> 
> The cmpxchg() and smp_store_release() act as the lock/unlock sequence
> with the proper barriers. Another important point is that the hpet value
> is visible to the other readers  before the sequence number. This is
> what the smp_store_release() is providing. cmpxchg is an actual barrier,
> even though smp_store_release() is not. However, the x86 architecture
> will guarantee the writes are in order, I think.

The contended case (where HPET_SEQ_LOCKED(seq)) doesn't do the cmpxchg.
 So it's entirely relying on the READ_ONCE() on the "reader" side and
the cmpxchg/smp_store_release() on the "writer".  This probably works in
practice, but I'm not sure it's guaranteed behavior.

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

#1461330

On 08/12/2016 10:01 AM, Waiman Long wrote:
> The reason for using a special lock is that I want both sequence number
> update and locking to be done together atomically. They can be made
> separate as is in the seqlock. However, that will make the code more
> complex to make sure that all the threads see a consistent set of lock
> state and sequence number.

Why do we need a sequence number?  The "cached" HPET itself could be used.

I'm thinking something like below could use a spinlock instead of the
doing a custom cmpxchg sequence.  The spin_is_locked() should allow the
contended "readers" to avoid using atomics.

spinlock_t hpet_lock;
u32 hpet_value;
...
{
	u32 old_hpet = READ_ONCE(hpet_value);
	u32 new_hpet;

	// need to ensure that the spin_is_locked() is ordered after
	// the READ_ONCE().
	smp_rmb();
	// spin_is_locked() doesn't do atomics
	if (!spin_is_locked(&hpet_lock) && spin_trylock(&hpet_lock)) {
		WRITE_ONCE(hpet_value, real_read_hpet());
		spin_unlock(&hpet_lock);
		return hpet_value;
	}
	// Contended case.  We spin here waiting for the guy who holds
	// the lock to write a new value to 'hpet_value'.
	//
	// We know that our old_hpet is older than our check for the
	// spinlock being locked. So, someone must either have already
	// updated it or be updating it.
	do {
		cpu_relax();
		// We do not do a rmb() here.  We don't need a guarantee
		// that this read is up-to-date, just that it will
		// _eventually_ see an up-to-date value.
		new_hpet = READ_ONCE(hpet_value);
	} while (old_hpet == new_hpet);
	return new_hpet;
}

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

#1461445

On Aug 12, 2016 9:31 PM, "Waiman Long" <waiman.long@hpe.com> wrote:
>
> On 08/12/2016 01:16 PM, Dave Hansen wrote:
>>
>> On 08/12/2016 10:01 AM, Waiman Long wrote:
>>>
>>> The reason for using a special lock is that I want both sequence number
>>> update and locking to be done together atomically. They can be made
>>> separate as is in the seqlock. However, that will make the code more
>>> complex to make sure that all the threads see a consistent set of lock
>>> state and sequence number.
>>
>> Why do we need a sequence number?  The "cached" HPET itself could be used.
>>
>> I'm thinking something like below could use a spinlock instead of the
>> doing a custom cmpxchg sequence.  The spin_is_locked() should allow the
>> contended "readers" to avoid using atomics.
>>
>> spinlock_t hpet_lock;
>> u32 hpet_value;
>> ...
>> {
>>         u32 old_hpet = READ_ONCE(hpet_value);
>>         u32 new_hpet;
>>
>>         // need to ensure that the spin_is_locked() is ordered after
>>         // the READ_ONCE().
>>         smp_rmb();
>>         // spin_is_locked() doesn't do atomics
>>         if (!spin_is_locked(&hpet_lock)&&  spin_trylock(&hpet_lock)) {
>>
>>                 WRITE_ONCE(hpet_value, real_read_hpet());
>>                 spin_unlock(&hpet_lock);
>>                 return hpet_value;
>>         }
>>         // Contended case.  We spin here waiting for the guy who holds
>>         // the lock to write a new value to 'hpet_value'.
>>         //
>>         // We know that our old_hpet is older than our check for the
>>         // spinlock being locked. So, someone must either have already
>>         // updated it or be updating it.
>>         do {
>>                 cpu_relax();
>>                 // We do not do a rmb() here.  We don't need a guarantee
>>                 // that this read is up-to-date, just that it will
>>                 // _eventually_ see an up-to-date value.
>>                 new_hpet = READ_ONCE(hpet_value);
>>         } while (old_hpet == new_hpet);
>>         return new_hpet;
>> }
>
>
> Yes, I think that work too. I will update my patch accordingly. Thanks for the input.

Why is Dave more convincing than I was a couple months ago when I
asked a similar question? :)

I don't think this is right.  If the HPET ever returns the same value
twice in a row (unlikely because it's generally too slow to read, but
it's plausible that someone will make a fast HPET some day), then this
could deadlock.

Also, does this code need to be NMI-safe?  This implementation is
deadlocky if it's called from an NMI.

The original code was wait-free, right?  That was a nice property, too.

--Andy

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

#1461459

On 08/12/2016 01:18 PM, Andy Lutomirski wrote:
> I don't think this is right.  If the HPET ever returns the same value
> twice in a row (unlikely because it's generally too slow to read, but
> it's plausible that someone will make a fast HPET some day), then this
> could deadlock.

True...

I guess that means we've got to do some kind of sequence counter
preferably in the same cacheline as the HPET value itself, or _something
that we guarantee to change on each write to the cached value.

> Also, does this code need to be NMI-safe?  This implementation is
> deadlocky if it's called from an NMI.

Urg.  Can't we just do

	if (in_nmi())
		return read_real_hpet();

?

> The original code was wait-free, right?  That was a nice property, too.

You mean no spins?  I don't think this one really spins ever either.

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

#1461461

On 08/12/2016 02:10 PM, Waiman Long wrote:
>> I don't think this is right.  If the HPET ever returns the same value
>> twice in a row (unlikely because it's generally too slow to read, but
>> it's plausible that someone will make a fast HPET some day), then this
>> could deadlock.
> 
> What is the deadlock scenario you are talking about?

A reader loops waiting for the HPET update by looking for the value to
change.  If the HPET updater does an update, but the HPET itself hasn't
advanced, it will write the same value as was there before.  The reader
will keep looping thinking there was no update.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web