Subject: Re: x86 instructions reordering
To: Manuel Bouyer <bouyer@antioche.lip6.fr>
From: TLorD <tld@tld.digitalcurse.com>
List: port-xen
Date: 03/25/2005 12:06:05
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Manuel Bouyer wrote:
| Hi,
| can newer x86 CPUs (hyperthreaded p4 in my case) reorder instructions,
| or memory writes ? If so, how can we impose barriers ?

Yes, it can reorder. I don't think you can impose barriers tho.

| Basically I have these 2 pieces of code in xen (NetBSD and linux), one sender
| and one receiver, using a piece of shared memory.
| The receiver:                          |     The sender:
|                                        |
| handle_event()                         |     send()
| {                                      |     {
|                                        |             a = shared_memory->a;
| again:                                 |             do_something;
|         a = shared_memory->a;          |             wmb();
|         __insn_barrier();              |             shared_memory->a = a + 1;
|         b = shared_memory->b;          |             mb()
|         while (b < a) {                |             if (shared_memory->b == a)
|                 /* do something */     |                     send_event();
|                 did_something = 1;     |     }
|                 b++;                   |
|         }                              |
|         __insn_barrier();              |
|         shared_memory->b = b;          |
|         __insn_barrier();              |
|         if (did_something)             |
|                 goto again;            |
| }                                      |

You have a deadlock in there, and no instruction reordering is the cause for
your issues.
I also don't think you need locks anywhere, since there is only one reader and
one writer per each [ab].

assume a == b, that is, queue is empty.
send()
handle_event starts, and gets to somewhere in the while() loop
meanwhile, send() again, and completes while handle_event is still in the
while() loop
handle_event() completes.

You now have b == a - 1 because s_m->b wasn't updated (so no send_event() took
place) and updated s_m->a wasn't read (so no queue emptying).

You might want to replace the while(b < a) with while(b < shared_memory->a),
which would always make a == b on exit, but still you could have issues if the
reader is faster than the writer:

shared_memory->a = a + 1;
- -- here
if (shared_memory->b == a)

if the reader is already working, you could end up with two reader threads.
Just make sure that can't happen and you should be fine.

Hope this helps, and keep up the good work
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)

iD8DBQFCQ/CcMiWEUf7YMGERAlF/AKCZNLkCN5ha0IN7fD/Rz9zoV8yC1QCgq9eo
+pI8/qLfhtoyi/44Jpakn50=
=8z8m
-----END PGP SIGNATURE-----