atomicity guarantees for threaded code

atomicity guarantees for threaded code

[Ker Lutyn]

Are there any guarantees for atomicity in threaded OCaml code? Or must I always
use a mutex? For example:

module StringMap = Map.Make (String)

let mapref = ref StringMap.empty

thread 1:

    mapref := StringMap.add key value !mapref

thread 2 through thread N:

    let value = StringMap.find key !mapref

Assume only thread 1 can update the reference. Is this code safe?



		
__________________________________
Do you Yahoo!?
Yahoo! Mail Address AutoComplete - You start. We finish.
http://promotions.yahoo.com/new_mail 

Re: [Caml-list] atomicity guarantees for threaded code

[David Brown]

On Fri, Oct 29, 2004 at 09:39:07AM -0700, Ker Lutyn wrote:

> thread 1:
> 
>     mapref := StringMap.add key value !mapref
> 
> thread 2 through thread N:
> 
>     let value = StringMap.find key !mapref
> 
> Assume only thread 1 can update the reference. Is this code safe?

As long as the reference write is atomic, which it is going to be, I would
suspect this is safe.  It probably would even be safe if multiple threads
updated the reference, but you might just drop entries.

Dave

Re: [Caml-list] atomicity guarantees for threaded code

[skaller]

On Sat, 2004-10-30 at 07:50, David Brown wrote:
> On Fri, Oct 29, 2004 at 09:39:07AM -0700, Ker Lutyn wrote:
> 
> > thread 1:
> > 
> >     mapref := StringMap.add key value !mapref
> > 
> > thread 2 through thread N:
> > 
> >     let value = StringMap.find key !mapref
> > 
> > Assume only thread 1 can update the reference. Is this code safe?
> 
> As long as the reference write is atomic, which it is going to be, I would
> suspect this is safe.  It probably would even be safe if multiple threads
> updated the reference, but you might just drop entries.

It isn't clear though. On x86 you can have 1 byte alignment
for an address. What happens if:

(a) thread 2 reads half an address, then gets a page fault
(b) thread 1 writes half an address, then gets a page fault,
(c) thread 1 writes the second half of the address
(d) thread 2 reads the second half of the WRONG address

The x86 can interrupt instructions in the middle ***
Actually, the 68K can do this too. On the x86 the
only way to get an atomic operation is on physical
memory, and by also locking the bus. CISC machines
get rather nasty ..

Bottom line: you have to use a specified atomic
access technique (eg sig_atomic_t, locks, etc) if you 
want to be sure an access is atomic.

It is likely as you say that there won't be a problem
on most processors (by which I mean the code
Ocaml generates will be effectively atomic wrt. threads)
and Ocaml could even guarrantee it, but there is a risk
for some processor extra code would have to generated
to ensure the guarrantee.

*** And I mean even with IRQs. In particular
I found a bug in the early 80186 hardware,
where if you used two prefixes such as with

	ES REP MOVB

then RTTI failed to restart the instruction correctly,
setting the PC to the REP instead of the ES prefix.
The MOVB instruction moves many bytes and must
be interruptible, even on the 186 which has no VM.


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] atomicity guarantees for threaded code

[David Brown]

On Sat, Oct 30, 2004 at 09:54:37AM +1000, skaller wrote:

> > As long as the reference write is atomic, which it is going to be, I would
> > suspect this is safe.  It probably would even be safe if multiple threads
> > updated the reference, but you might just drop entries.
> 
> It isn't clear though. On x86 you can have 1 byte alignment
> for an address. What happens if:

But, a reference in ocaml will always be in a block, which will always be
aligned.  Even x86 will be atomic with a 32-bit transfer that is aligned.

Dave

Re: [Caml-list] atomicity guarantees for threaded code

[skaller]

On Sat, 2004-10-30 at 10:32, David Brown wrote:
> On Sat, Oct 30, 2004 at 09:54:37AM +1000, skaller wrote:
> 
> > > As long as the reference write is atomic, which it is going to be, I would
> > > suspect this is safe.  It probably would even be safe if multiple threads
> > > updated the reference, but you might just drop entries.
> > 
> > It isn't clear though. On x86 you can have 1 byte alignment
> > for an address. What happens if:
> 
> But, a reference in ocaml will always be in a block, which will always be
> aligned. 

On what boundary?

>  Even x86 will be atomic with a 32-bit transfer that is aligned.

But perhaps not a 64 bit one.

Part of my argument was that it is implementation
dependent. In particular, a page fault is only one
kind of interrupt. It is possible, for example,
to get another IRQ right in the middle of a transfer
from memory .. and interrupt the transfer. And that
IRQ could actually cause the page from which the
load was occuring to be swapped out .. meaning
it may not be necessary to be near a page boundary
to get a page fault... and thus the alignment
may not matter.

As I indicated some instructions on some processors
aren't atomic, particularly CISC machines.. it may be
that loading and storing isn't such an interruptible
instruction, but I'm not sure .. without checking
the x86 hardware manual. Certainly 48 bit loads
on a x386 can cause segmentation faults (I mean,
the whole thing is *designed* to do that) .. however
these don't normally apply to Unix like systems that
aren't capable of using segmented addressing
(in user space).

So I would guess you are right for all OS Ocaml supports.
Even so I'd be loath to rely on such a guess until
the Ocaml team asserted the guarrantee in the manual.

I wouldn't do it in C, because of the wide class
of platforms it applies to .. but Ocaml doesn't intend
to handle such a wide class.

If the guarrantee was made, it could simplify some
Ocaml programming significantly, and thus possibly
improve performance.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] atomicity guarantees for threaded code

[David Brown]

On Sat, Oct 30, 2004 at 11:07:28AM +1000, skaller wrote:

> > But, a reference in ocaml will always be in a block, which will always be
> > aligned. 
> 
> On what boundary?

> >  Even x86 will be atomic with a 32-bit transfer that is aligned.
> 
> But perhaps not a 64 bit one.

I would argue that on a machine with 64-bit addresses, you can assume that
64-bit, aligned loads and stores will be atomic.  There is just too much
code that wouldn't work.  Other assumptions are hard to make, though.

Dave

Re: [Caml-list] atomicity guarantees for threaded code

[skaller]

On Sat, 2004-10-30 at 12:07, David Brown wrote:

> I would argue that on a machine with 64-bit addresses, you can assume that
> 64-bit, aligned loads and stores will be atomic.

You can claim that this is the case a lot of the time.
But it isn't guarranteed by ISO C. To actually argue it
should be guarranteed you'd need to join WG14 and actually
propose it... :)

For Ocaml, you could ask Xavier ..

>   There is just too much
> code that wouldn't work. 

There is lots of code that actually *doesn't* work,
so this isn't much of an argument.. :)

I do agree I have been pushing the limits of imagination
playing Devil's Advocate .. you're probably right.
But that isn't a guarrantee.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net