Skip to contentSkip to conversation

different kinds of memory barrier

Question Yubin Ruan 3 participants 10 messages Feb 13, 2017 – Feb 18, 2017 2 messages not in the archive

lore
Share & tools
lore

Yubin Ruan

author
#0 lore raw

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

regards,
Yubin Ruan

#1 lore raw
Quoted 23 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

Quoted 8 lines

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

author
#2 lore raw
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 8 lines
Quoted 8 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 11 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

Quoted 9 lines

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

regrads,
Yubin Ruan

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

author
#5 lore raw
Quoted 37 lines · Yubin Ruan
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Yubin Ruan
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 7 lines
Quoted 7 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 6 lines
Quoted 6 lines

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

regards,
Yubin Ruan

Quoted 63 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

    Thread 0        Thread 1
    --------        --------
    WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
    smp_wmb();        smp_mb();
    WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

    https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
    https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 26 lines
Quoted 26 lines
Quoted 17 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

Quoted 5 lines

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

regrads,
Yubin Ruan

#6 lore raw
Quoted 40 lines · Yubin Ruan
Quoted 37 lines · Yubin Ruan
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Yubin Ruan
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 7 lines
Quoted 7 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 8 lines
Quoted 5 lines
Quoted 5 lines

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

It does include Alpha. Remember that Alpha's peculiarities occur when you -don't- have full memory barriers. If you have a full memory barrier between each pair of accesses, then everything will be ordered on pretty much every type of CPU.

The one exception that I am aware of is Itanium, which also requires that the stores be converted to store-release instructions.

Thanx, Paul

Quoted 67 lines

regards,
Yubin Ruan

Quoted 63 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

   Thread 0        Thread 1
   --------        --------
   WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
   smp_wmb();        smp_mb();
   WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 26 lines
Quoted 26 lines
Quoted 17 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

Quoted 5 lines

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

regrads,
Yubin Ruan

author
#7 lore raw
Quoted 47 lines · Paul E. McKenney
Quoted 46 lines · Yubin Ruan
Quoted 42 lines · Yubin Ruan
Quoted 39 lines · Paul E. McKenney
Quoted 25 lines · Yubin Ruan
Quoted 24 lines · Paul E. McKenney
Quoted 23 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

Quoted 7 lines
Quoted 3 lines
Quoted 3 lines

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

Quoted 8 lines
Quoted 2 lines

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

It does include Alpha. Remember that Alpha's peculiarities occur when you -don't- have full memory barriers. If you have a full memory barrier between each pair of accesses, then everything will be ordered on pretty much every type of CPU.

You mean this change would work for Alpha?

Quoted 21 lines

1 struct el *insert(long key, long data)
2 {

3     struct el *p;
4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data;

9 smp_mb(); /* changed smp_wmb()' to smp_mb()' */

10 head.next = p;
11 spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {

16    struct el *p;
17    p = head.next;
18    while (p != &head) {
Quoted 8 lines

19 /* BUG ON ALPHA!!! */
20 if (p->key == key) {
21 return (p);
22 }
23 p = p->next;
24 };
25 return (NULL);
26 }

regards,
Yubin Ruan

Quoted 73 lines

The one exception that I am aware of is Itanium, which also requires that the stores be converted to store-release instructions.

Thanx, Paul

Quoted 67 lines

regards,
Yubin Ruan

Quoted 63 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

   Thread 0        Thread 1
   --------        --------
   WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
   smp_wmb();        smp_mb();
   WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 26 lines
Quoted 26 lines
Quoted 17 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

Quoted 5 lines

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

regrads,
Yubin Ruan

#8 lore raw
Quoted 51 lines · Yubin Ruan
Quoted 50 lines · Paul E. McKenney
Quoted 48 lines · Yubin Ruan
Quoted 37 lines · Yubin Ruan
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Yubin Ruan
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 7 lines
Quoted 7 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 5 lines
Quoted 5 lines

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

Quoted 18 lines
Quoted 5 lines

It does include Alpha. Remember that Alpha's peculiarities occur when you -don't- have full memory barriers. If you have a full memory barrier between each pair of accesses, then everything will be ordered on pretty much every type of CPU.

You mean this change would work for Alpha?

Quoted 10 lines

1 struct el *insert(long key, long data)
2 {

3     struct el *p;
4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data;

9 smp_mb(); /* changed smp_wmb()' to smp_mb()' */

No, this would not help.

Quoted 10 lines
Quoted 10 lines

10 head.next = p;
11 spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {

16    struct el *p;
17    p = head.next;
18    while (p != &head) {

19 /* BUG ON ALPHA!!! */

		smp_mb();

This is where you need the additional barrier. Note that in the Linux kernel, rcu_dereference() and similar primitives provide this barrier in Alpha builds.

Thanx, Paul

Quoted 85 lines
Quoted 7 lines

20 if (p->key == key) {
21 return (p);
22 }
23 p = p->next;
24 };
25 return (NULL);
26 }

regards,
Yubin Ruan

Quoted 73 lines

The one exception that I am aware of is Itanium, which also requires that the stores be converted to store-release instructions.

Thanx, Paul

Quoted 67 lines

regards,
Yubin Ruan

Quoted 63 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

   Thread 0        Thread 1
   --------        --------
   WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
   smp_wmb();        smp_mb();
   WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 26 lines
Quoted 26 lines
Quoted 17 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

Quoted 5 lines

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

regrads,
Yubin Ruan

author
#9 lore raw
Quoted 84 lines · Paul E. McKenney
Quoted 51 lines · Yubin Ruan
Quoted 50 lines · Paul E. McKenney
Quoted 48 lines · Yubin Ruan
Quoted 37 lines · Yubin Ruan
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Yubin Ruan
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 7 lines
Quoted 7 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 5 lines
Quoted 5 lines

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

Quoted 18 lines
Quoted 5 lines

It does include Alpha. Remember that Alpha's peculiarities occur when you -don't- have full memory barriers. If you have a full memory barrier between each pair of accesses, then everything will be ordered on pretty much every type of CPU.

You mean this change would work for Alpha?

Quoted 10 lines

1 struct el *insert(long key, long data)
2 {

3     struct el *p;
4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data;

9 smp_mb(); /* changed smp_wmb()' to smp_mb()' */

No, this would not help.

Quoted 10 lines
Quoted 10 lines

10 head.next = p;
11 spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {

16    struct el *p;
17    p = head.next;
18    while (p != &head) {

19 /* BUG ON ALPHA!!! */

Quoted 8 lines
		smp_mb();

This is where you need the additional barrier. Note that in the Linux kernel, rcu_dereference() and similar primitives provide this barrier in Alpha builds.

Thanx, Paul

Got it. So, regarding to memory barrier, I think I was confused with "how one CPU deal with the the memory barriers of another CPU's memory". As you have said, for any CPU, "all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb()", and all CPU "agree" with this. But that doesn't mean the other CPUs will regard this access sequence(e.g, Alpha). Right ?

sorry for my annoying obsession with this. Thanks.

regards,
Yubin Ruan

Quoted 86 lines
Quoted 85 lines
Quoted 7 lines

20 if (p->key == key) {
21 return (p);
22 }
23 p = p->next;
24 };
25 return (NULL);
26 }

regards,
Yubin Ruan

Quoted 73 lines

The one exception that I am aware of is Itanium, which also requires that the stores be converted to store-release instructions.

Thanx, Paul

Quoted 67 lines

regards,
Yubin Ruan

Quoted 63 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

   Thread 0        Thread 1
   --------        --------
   WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
   smp_wmb();        smp_mb();
   WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 26 lines
Quoted 26 lines
Quoted 17 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

Quoted 5 lines

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

regrads,
Yubin Ruan

#10 lore raw
Quoted 94 lines · Yubin Ruan
Quoted 84 lines · Paul E. McKenney
Quoted 51 lines · Yubin Ruan
Quoted 50 lines · Paul E. McKenney
Quoted 48 lines · Yubin Ruan
Quoted 37 lines · Yubin Ruan
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Yubin Ruan
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 7 lines
Quoted 7 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 5 lines
Quoted 5 lines

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

Quoted 18 lines
Quoted 5 lines

It does include Alpha. Remember that Alpha's peculiarities occur when you -don't- have full memory barriers. If you have a full memory barrier between each pair of accesses, then everything will be ordered on pretty much every type of CPU.

You mean this change would work for Alpha?

Quoted 10 lines

1 struct el *insert(long key, long data)
2 {

3     struct el *p;
4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data;

9 smp_mb(); /* changed smp_wmb()' to smp_mb()' */

No, this would not help.

Quoted 10 lines
Quoted 10 lines

10 head.next = p;
11 spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {

16    struct el *p;
17    p = head.next;
18    while (p != &head) {

19 /* BUG ON ALPHA!!! */

Quoted 8 lines
		smp_mb();

This is where you need the additional barrier. Note that in the Linux kernel, rcu_dereference() and similar primitives provide this barrier in Alpha builds.

Thanx, Paul

Quoted 6 lines

Got it. So, regarding to memory barrier, I think I was confused with "how one CPU deal with the the memory barriers of another CPU's memory". As you have said, for any CPU, "all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb()", and all CPU "agree" with this. But that doesn't mean the other CPUs will regard this access sequence(e.g, Alpha). Right ?

Hi Yubin,

I'd rather rephrase your observation as follows:

For any CPU, "all accesses by any CPU preceding a
given smp_mb() happened before any accesses by that same CPU following that same smp_mb()", and all CPU "agree" with this as long as memory ordering is ensured by proper memory barriers or alternative means such as data dependency or control dependency.

Note that Alpha does not respect data dependency, and it requires *expensive* full memory barriers instead.

Does this answer your question?

Thanks, Akira

Quoted 97 lines

sorry for my annoying obsession with this. Thanks.

regards,
Yubin Ruan

Quoted 79 lines
Quoted 79 lines
Quoted 7 lines

20 if (p->key == key) {
21 return (p);
22 }
23 p = p->next;
24 };
25 return (NULL);
26 }

regards,
Yubin Ruan

Quoted 68 lines

The one exception that I am aware of is Itanium, which also requires that the stores be converted to store-release instructions.

Thanx, Paul

Quoted 63 lines

regards,
Yubin Ruan

Quoted 60 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

   Thread 0        Thread 1
   --------        --------
   WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
   smp_wmb();        smp_mb();
   WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

Quoted 7 lines
Quoted 6 lines
Quoted 5 lines
Quoted 4 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

regrads,
Yubin Ruan

--
To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

author
#11 lore raw
Quoted 112 lines · Akira Yokosawa
Quoted 94 lines · Yubin Ruan
Quoted 84 lines · Paul E. McKenney
Quoted 51 lines · Yubin Ruan
Quoted 50 lines · Paul E. McKenney
Quoted 48 lines · Yubin Ruan
Quoted 37 lines · Yubin Ruan
Quoted 34 lines · Paul E. McKenney
Quoted 32 lines · Yubin Ruan
Quoted 20 lines · Paul E. McKenney
Quoted 19 lines · Yubin Ruan

It have been mentioned in the book that there are three kinds of memory barriers: smp_rmb, smp_wmb, smp_mb

I am confused about their actual semantic:

The book says that(B.5 paragraph 2, perfbook2017.01.02a):

for smp_rmb():
"The effect of this is that a read memory barrier orders
only loads on the CPU that executes it, so that all loads preceding the read memory barrier will appear to have completed before any load following the read memory barrier"

for smp_wmb():
"so that all stores preceding the write memory barrier will
appear to have completed before any store following the write memory barrier"

Quoted 7 lines
Quoted 7 lines

I wonder, is there any primitive "X" which can guarantees:
"that all 'loads' preceding the X will appear to have completed
before any *store* following the X "

and similarly:
"that all 'store' preceding the X will appear to have completed
before any *load* following the X "

I am reading your the material you provided.
So, there is no short answer(yes/no) to the questions above?(I mean the primitive X)

Quoted 5 lines
Quoted 5 lines

For smp_mb(), the full memory barrier, things are pretty simple. All CPUs will agree that all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb(). Full memory barriers are also transitive, so that you can reason (relatively) easily about situations involving many CPUs.

One more thing about the full memory barrier. You say *all CPU agree*. It does not include Alpha, right?

Quoted 18 lines
Quoted 5 lines

It does include Alpha. Remember that Alpha's peculiarities occur when you -don't- have full memory barriers. If you have a full memory barrier between each pair of accesses, then everything will be ordered on pretty much every type of CPU.

You mean this change would work for Alpha?

Quoted 10 lines

1 struct el *insert(long key, long data)
2 {

3     struct el *p;
4     p = kmalloc(sizeof(*p), GFP_ATOMIC);
5     spin_lock(&mutex);
6     p->next = head.next;
7     p->key = key;
8     p->data = data;

9 smp_mb(); /* changed smp_wmb()' to smp_mb()' */

No, this would not help.

Quoted 10 lines
Quoted 10 lines

10 head.next = p;
11 spin_unlock(&mutex);
12 }
13
14 struct el *search(long key)
15 {

16    struct el *p;
17    p = head.next;
18    while (p != &head) {

19 /* BUG ON ALPHA!!! */

Quoted 8 lines
		smp_mb();

This is where you need the additional barrier. Note that in the Linux kernel, rcu_dereference() and similar primitives provide this barrier in Alpha builds.

Thanx, Paul

Quoted 6 lines

Got it. So, regarding to memory barrier, I think I was confused with "how one CPU deal with the the memory barriers of another CPU's memory". As you have said, for any CPU, "all accesses by any CPU preceding a given smp_mb() happened before any accesses by that same CPU following that same smp_mb()", and all CPU "agree" with this. But that doesn't mean the other CPUs will regard this access sequence(e.g, Alpha). Right ?

Hi Yubin,

I'd rather rephrase your observation as follows:

For any CPU, "all accesses by any CPU preceding a
given smp_mb() happened before any accesses by that same CPU following that same smp_mb()", and all CPU "agree" with this as long as memory ordering is ensured by proper memory barriers or alternative means such as data dependency or control dependency.

Quoted 6 lines

Note that Alpha does not respect data dependency, and it requires *expensive* full memory barriers instead.

Does this answer your question?

Thanks, Akira

Yes, I think I understand now. Thanks!

regards,
Yubin Ruan

Quoted 98 lines
Quoted 98 lines

sorry for my annoying obsession with this. Thanks.

regards,
Yubin Ruan

Quoted 79 lines
Quoted 79 lines
Quoted 7 lines

20 if (p->key == key) {
21 return (p);
22 }
23 p = p->next;
24 };
25 return (NULL);
26 }

regards,
Yubin Ruan

Quoted 68 lines

The one exception that I am aware of is Itanium, which also requires that the stores be converted to store-release instructions.

Thanx, Paul

Quoted 63 lines

regards,
Yubin Ruan

Quoted 60 lines
Quoted 20 lines

For smp_rmb() and smp_wmb(), not so much. The canonical example showing the complexity of smp_wmb() is called "R":

   Thread 0        Thread 1
   --------        --------
   WRITE_ONCE(x, 1);    WRITE_ONCE(y, 2);
   smp_wmb();        smp_mb();
   WRITE_ONCE(y, 1);    r1 = READ_ONCE(x);

One might hope that if the final value of y is 2, then the value of r1 must be 1. People hoping this would be disappointed, because there really is hardware that will allow the outcome y == 1 && r1 == 0.

See the following URL for many more examples of this sort of thing:

   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

For more information, including some explanation of the nomenclature, see:

Quoted 9 lines
   https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

There are formal memory models that account for this, and in fact this appendix is slated to be rewritten based on some work a group of us have been doing over the past two years or so. A tarball containing a draft of this work is attached. I suggested starting with index.html. If you get a chance to look it over, I would value any suggestions that you might have.

Thanks for your reply. I will take some time to read those materials. Discussions with you really help eliminate some of my doubts. Hopefully we can have more discussions in the future.

regards,
Yubin Ruan

Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 4 lines

I know I can use the general smp_mb() for that, but that is a little too general.

Do I miss/mix anything ?

Well, the memory-ordering material is a bit dated. There is some work underway to come up with a better model, and I presented on it a couple weeks ago:

http://www.rdrop.com/users/paulmck/scalability/paper/LinuxMM.2017.01.19a.LCA.pdf

This presentation calls out a tarball that includes some .html files that have much better explanations, and this wording will hopefully be reflected in an upcoming version of the book. Here is a direct URL for the tarball:

http://www.rdrop.com/users/paulmck/scalability/paper/LCA-LinuxMemoryModel.2017.01.15a.tgz

Thanx, Paul

Quoted 7 lines
Quoted 6 lines
Quoted 5 lines
Quoted 4 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

regrads,
Yubin Ruan

--
To unsubscribe from this list: send the line "unsubscribe perfbook" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html