Skip to contentSkip to conversation

sequence lock in Linux

DISCUSSION Mathieu Desnoyers 4 participants 11 messages Jun 11, 2010

lore
Share & tools
lore
#0 lore raw

Hi Paul,

(CCing lkml)

Is it just me, or the following code:

static __always_inline unsigned read_seqbegin(const seqlock_t *sl)

{
        unsigned ret;

repeat:

        ret = sl->sequence;
        smp_rmb();
        if (unlikely(ret & 1)) {
                cpu_relax();
                goto repeat;
        }

        return ret;
}

could use a ACCESS_ONCE() around the sl->sequence read ? I'm concerned about the compiler generating code that reads the sequence number chunkwise.

The same apply to all other reads of the sequence number in seqlock.h (including the retry code).

Thoughts ?

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#1 lore raw
Quoted 21 lines · Mathieu Desnoyers

Hi Paul,

(CCing lkml)

Is it just me, or the following code:

static __always_inline unsigned read_seqbegin(const seqlock_t *sl)

{
        unsigned ret;

repeat:

        ret = sl->sequence;
        smp_rmb();
        if (unlikely(ret & 1)) {
                cpu_relax();
                goto repeat;
        }

        return ret;
}
Quoted 7 lines

could use a ACCESS_ONCE() around the sl->sequence read ? I'm concerned about the compiler generating code that reads the sequence number chunkwise.

The same apply to all other reads of the sequence number in seqlock.h (including the retry code).

Thoughts ?

Doesn't gcc guarantee that accesses to aligned basic types that fit into a machine word are loaded and stored in one shot? Now, gcc might choose to load twice (or to merge loads) due to things like register pressure, but given that ->sequence is an int, gcc should not be accessing it (say) bytewise on any platform supporting 32-bit accesses.

Or am I suffering from wishful thinking here?

Thanx, Paul

#2 lore raw
Quoted 30 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 21 lines · Mathieu Desnoyers

Hi Paul,

(CCing lkml)

Is it just me, or the following code:

static __always_inline unsigned read_seqbegin(const seqlock_t *sl)

{
        unsigned ret;

repeat:

        ret = sl->sequence;
        smp_rmb();
        if (unlikely(ret & 1)) {
                cpu_relax();
                goto repeat;
        }

        return ret;
}
Quoted 7 lines

could use a ACCESS_ONCE() around the sl->sequence read ? I'm concerned about the compiler generating code that reads the sequence number chunkwise.

The same apply to all other reads of the sequence number in seqlock.h (including the retry code).

Thoughts ?

Quoted 7 lines

Doesn't gcc guarantee that accesses to aligned basic types that fit into a machine word are loaded and stored in one shot? Now, gcc might choose to load twice (or to merge loads) due to things like register pressure, but given that ->sequence is an int, gcc should not be accessing it (say) bytewise on any platform supporting 32-bit accesses.

Or am I suffering from wishful thinking here?

Hopefully not. I might be the one suffering from extreme compiler distrust here. ;-)

Mathieu

Quoted 2 lines

Thanx, Paul

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#3 lore raw
In reply to Mathieu Desnoyers
Quoted 15 lines · Mathieu Desnoyers

Is it just me, or the following code:

static __always_inline unsigned read_seqbegin(const seqlock_t *sl) {
       unsigned ret;

repeat:
       ret = sl->sequence;
       smp_rmb();
       if (unlikely(ret & 1)) {
               cpu_relax();
               goto repeat;
       }

Quoted 5 lines

       return ret;
}

could use a ACCESS_ONCE() around the sl->sequence read ? I'm concerned about the compiler generating code that reads the sequence number chunkwise.

What compiler would do that? That would seem to be a compiler bug, or a compiler that is just completely crazy.

But it wouldn't be _wrong_ to make it do ACCESS_ONCE(). I just suspect that any compiler that cares is not a compiler worth worrying about, and the compiler should be shot in the head rather than us necessarily worrying about it.

There is no way a sane compiler can do anything but one read anyway. We do end up using all the bits (for the "return ret") part, so a compiler that reads the low bit separately is just being a totally moronic one - we wouldn't want to touch such a stupid compiler with a ten-foot pole.

But at the same time, ACCESS_ONCE() ends up being a reasonable hint to programmers, so I wouldn't object to it. I just don't think we should pander to "compilers can be crazy". If compilers are crazy, we shouldn't use them.

Linus

#4 lore raw
Quoted 17 lines · Linus Torvalds
Quoted 15 lines · Mathieu Desnoyers

Is it just me, or the following code:

static __always_inline unsigned read_seqbegin(const seqlock_t *sl) {
       unsigned ret;

repeat:
       ret = sl->sequence;
       smp_rmb();
       if (unlikely(ret & 1)) {
               cpu_relax();
               goto repeat;
       }

Quoted 8 lines
Quoted 5 lines

       return ret;
}

could use a ACCESS_ONCE() around the sl->sequence read ? I'm concerned about the compiler generating code that reads the sequence number chunkwise.

What compiler would do that? That would seem to be a compiler bug, or a compiler that is just completely crazy.

The reason that the C standard permits this is to allow for things like 8-bit CPUs, which are simply unable to load or store 32-bit quantities except by doing it chunkwise. But I don't expect the Linux kernel to boot on these, and certainly not on any of the ones that I have used!

I most definitely remember seeing a gcc guarantee that loads and stores would be done in one instruction whenever the hardware supported this, but I am not finding it today. :-(

Thanx, Paul

Quoted 17 lines

But it wouldn't be _wrong_ to make it do ACCESS_ONCE(). I just suspect that any compiler that cares is not a compiler worth worrying about, and the compiler should be shot in the head rather than us necessarily worrying about it.

There is no way a sane compiler can do anything but one read anyway. We do end up using all the bits (for the "return ret") part, so a compiler that reads the low bit separately is just being a totally moronic one - we wouldn't want to touch such a stupid compiler with a ten-foot pole.

But at the same time, ACCESS_ONCE() ends up being a reasonable hint to programmers, so I wouldn't object to it. I just don't think we should pander to "compilers can be crazy". If compilers are crazy, we shouldn't use them.

Linus

#5 lore raw
Quoted 10 lines · Paul E. McKenney

The reason that the C standard permits this is to allow for things like 8-bit CPUs, which are simply unable to load or store 32-bit quantities except by doing it chunkwise. But I don't expect the Linux kernel to boot on these, and certainly not on any of the ones that I have used!

I most definitely remember seeing a gcc guarantee that loads and stores would be done in one instruction whenever the hardware supported this, but I am not finding it today. :-(

What gcc does not -- and should not -- guarantee is that accessing a non-volatile member is done exactly once. As Mathieu pointed out, it can choose to drop it due to register pressure and load it again.

What is possibly a much bigger risk -- since this is an inline -- is that the value is cached from a previous piece of code, *or* that since the structure is const(!) that the second read in the repeat loop is elided. Presumably current versions of gcc don't do that across a memory clobber, but that doesn't seem entirely out of the question.

-hpa

#6 lore raw
Quoted 15 lines · H. Peter Anvin
Quoted 9 lines · Paul E. McKenney

The reason that the C standard permits this is to allow for things like 8-bit CPUs, which are simply unable to load or store 32-bit quantities except by doing it chunkwise. But I don't expect the Linux kernel to boot on these, and certainly not on any of the ones that I have used!

I most definitely remember seeing a gcc guarantee that loads and stores would be done in one instruction whenever the hardware supported this, but I am not finding it today. :-(

What gcc does not -- and should not -- guarantee is that accessing a non-volatile member is done exactly once. As Mathieu pointed out, it can choose to drop it due to register pressure and load it again.

Quoted 5 lines

What is possibly a much bigger risk -- since this is an inline -- is that the value is cached from a previous piece of code, *or* that since the structure is const(!) that the second read in the repeat loop is elided. Presumably current versions of gcc don't do that across a memory clobber, but that doesn't seem entirely out of the question.

Memory barriers in the sequence-lock code prevent this, assuming, as you point out, that memory clobber works (but if it doesn't, it should be fixed):

o write_seqlock() and write_tryseqlock() each have an smp_wmb()
following the increment. Ditto for write_seqcount_begin().

o write_sequnlock() has an smp_wmb() preceding the increment,

	and ditto for write_seqcount_end().  There are thus two smp_wmb()
	calls between the increments in the usual code sequence:

		write_seqlock(&l);
		do_something();
		write_sequnlock();

o read_seqbegin() has an smp_rmb() following its read from

	->sequence.  Ditto for read_seqcount_begin().

o read_seqretry() has an smp_rmb() preceding its read from

	->sequence, and ditto for read_seqcount_retry().  There are thus
	two smp_wmb() calls between the reads in the usual code sequence:

		do {
			s = read_seqbegin(&l);
			read_something();
		} while read_seqretry(&l, s);

So sequence locks should be pretty safe, at least as far as this vulnerability is concerned. ;-)

Thanx, Paul

#7 lore raw
Quoted 3 lines · Paul E. McKenney

Memory barriers in the sequence-lock code prevent this, assuming, as you point out, that memory clobber works (but if it doesn't, it should be fixed):

The constness is my main concern. It's not clear to me that "memory" is meant to imply that const memory areas without volatile can be clobbered.

-hpa

#8 lore raw
Quoted 7 lines · H. Peter Anvin
Quoted 3 lines · Paul E. McKenney

Memory barriers in the sequence-lock code prevent this, assuming, as you point out, that memory clobber works (but if it doesn't, it should be fixed):

The constness is my main concern. It's not clear to me that "memory" is meant to imply that const memory areas without volatile can be clobbered.

Ah! I was assuming that gcc treated "memory" as it would an call to a function in some other compilation unit. In that case, the compiler could not count on the "const" on the argument, given the possibility that the called function might gain a reference to the same memory locations in a non-const manner, right?

Thanx, Paul

#9 lore raw
Quoted 9 lines · Paul E. McKenney
Quoted 7 lines · H. Peter Anvin
Quoted 3 lines · Paul E. McKenney

Memory barriers in the sequence-lock code prevent this, assuming, as you point out, that memory clobber works (but if it doesn't, it should be fixed):

The constness is my main concern. It's not clear to me that "memory" is meant to imply that const memory areas without volatile can be clobbered.

Quoted 7 lines

Ah! I was assuming that gcc treated "memory" as it would an call to a function in some other compilation unit. In that case, the compiler could not count on the "const" on the argument, given the possibility that the called function might gain a reference to the same memory locations in a non-const manner, right?

Thanx, Paul

Right.

-hpa

#10 lore raw
In reply to Linus Torvalds
Quoted 31 lines · * Linus Torvalds ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Is it just me, or the following code:

static __always_inline unsigned read_seqbegin(const seqlock_t *sl) {
       unsigned ret;

repeat:
       ret = sl->sequence;
       smp_rmb();
       if (unlikely(ret & 1)) {
               cpu_relax();
               goto repeat;
       }

Quoted 5 lines

       return ret;
}

could use a ACCESS_ONCE() around the sl->sequence read ? I'm concerned about the compiler generating code that reads the sequence number chunkwise.

What compiler would do that? That would seem to be a compiler bug, or a compiler that is just completely crazy.

But it wouldn't be _wrong_ to make it do ACCESS_ONCE(). I just suspect that any compiler that cares is not a compiler worth worrying about, and the compiler should be shot in the head rather than us necessarily worrying about it.

Quoted 5 lines

There is no way a sane compiler can do anything but one read anyway. We do end up using all the bits (for the "return ret") part, so a compiler that reads the low bit separately is just being a totally moronic one - we wouldn't want to touch such a stupid compiler with a ten-foot pole.

If for some reason it is better (faster for -O2, smaller code for -Os) on a given architecture to read the low bits separately from the rest and populate two different registers, one for the test and the other for the return value, then a not-so-moronic compiler might actually do this. One reason I could see for generating this kind of code is compiling with -Os, if the kind of behavior I describe above generates smaller code.

Quoted 5 lines

But at the same time, ACCESS_ONCE() ends up being a reasonable hint to programmers, so I wouldn't object to it. I just don't think we should pander to "compilers can be crazy". If compilers are crazy, we shouldn't use them.

I'm just afraid about the possibility that non-crazy compilers might actually have a good reason to do this we haven't thought of yet.

FWIW, in the userspace RCU library, I wrapped all non-protected accesses to shared word-sized aligned variables (e.g. rcu_assign_pointer(), rcu_dereference_pointer(), ..) with LOAD_SHARED() and STORE_SHARED() accessors, which are basically just volatile loads and stores.

That's just me making absolutely sure the compiler won't perform anything chunkwise nor perform multiple loads. It also ensures we are somewhat ready for upcoming architectures with non-coherent caches. Having all these accesses in a convenient macro makes it much easier to insert cache flushes whenever needed.

Thanks,

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com