<html><head><base href="x-msg://2207/"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div><span class="Apple-style-span" style="font-size: medium; ">On 18 Dec 2009, at 14:32, Jay K wrote:</span></div></span></span></span></span></span></span></span></span></div></span></span></div><div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Ah, ok.<br> <br>btw another "common" primitive is InterlockedCompareExchange"Double".<br></div></span></blockquote><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">As in InterlockedCompareExchange64 that's been in x86 a while and InterlockedCompareExchange128 that is newer.<br> <br>There are also often alignment requirements for these things, like to not cross cache line boundaries.</div></span></blockquote><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">We're already ok that way?<br>At least for globals?<br></div></span></blockquote><div><br></div><div>I think so. Need to check.</div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; "> <br> - Jay<br><br> <br><hr id="stopSpelling">Subject: Re: [M3devel] cas/casp?<br>From:<span class="Apple-converted-space"> </span><a href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</a><br>Date: Fri, 18 Dec 2009 14:12:44 -0500<br>CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>To:<span class="Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br><br><div><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div style="word-wrap: break-word; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal 12px/normal Helvetica; white-space: normal; letter-spacing: normal; color: rgb(0, 0, 0); word-spacing: 0px; "><div><span class="ecxApple-style-span" style="font-size: medium; ">On 18 Dec 2009, at 14:06, Jay K wrote:</span></div></span></span></span></span></span></span></span></span></div></span></span></div><div><br class="ecxApple-interchange-newline"><blockquote><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal medium/normal Helvetica; white-space: normal; letter-spacing: normal; word-spacing: 0px; "><div class="ecxhmmessage" style="font-family: Verdana; font-size: 10pt; ">oh. I already got it working. ok.<br><br>Atomic confuses me in a few ways.<br> <br>I find it terribly confusing on Windows that there are separate compiler and memory fences.<br>I'd like there to be a very simple full fence that forces all reads/writes before it to finish before any reads/writes after it, both for the compiler and processor.<br></div></span></blockquote><div><br></div><div>MemoryFence does that. CompilerFence is strictly weaker than MemoryFence.</div><br><blockquote><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal medium/normal Helvetica; white-space: normal; letter-spacing: normal; word-spacing: 0px; "><div class="ecxhmmessage" style="font-family: Verdana; font-size: 10pt; ">It makes no sense to me to allow the processor or compiler to reorder but not both.<br> <br> <br>What is weak cas?<br></div></span></blockquote><div><br></div><div>It's a CAS that can fail spuriously. i.e., even if the old value was ==.</div><br><blockquote><span class="ecxApple-style-span" style="text-transform: none; text-indent: 0px; border-collapse: separate; font: normal normal normal medium/normal Helvetica; white-space: normal; letter-spacing: normal; word-spacing: 0px; "><div class="ecxhmmessage" style="font-family: Verdana; font-size: 10pt; ">Is that loadlocked/storecondition and the caller can loop?<br> <br> <br>Um. There is the Windows terminology InterlockedWhatever.<br>There is the gccc builtins.<br>Can we "sound" close to one of them?<br>Or is this based on some other widely known system?<br></div></span></blockquote><div><br></div><div>The Atomic interface I posted is based on a proposal for the C++ standard:</div><div><br></div><div><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2047.html">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2047.html</a></div><br><blockquote><div class="ecxhmmessage" style="font-family: Verdana; font-size: 10pt; "> And we don't care about older x86 processors like 386?486 I assume?<br>There seem to have been at least two leaps in functionality here.<br>Old Win32 operating systems provide very few interlocked functions.<br>They provide increment and decrement, that only return <0, 0, >0 of the new value.<br>And Exchange. (This is based on the Visual C++ 2.0 winbase.h)<br>All just on 32bit values.<br> <br>Later on there is a much larger suite, Exchange, ExchangeAdd, Inc/Dec that return new value, all on 32 bit values.<br> <br>And then later, stuff added for 16 values, bit operations, maybe 8 bit values, and, or, xor. I don't think this requires newer processors though.<br> <br>And then also at some point InterlockedCompareExchange64 which requires the "newest" processors, but is still quite old.<br>>From this you can synthesize inc/dec/and/or/xor with loops and that is done with inline functions in winbase.h.<br> <br> <br> - Jay<br><br> <br>> From:<span class="ecxApple-converted-space"> </span><a href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</a><br>> Date: Fri, 18 Dec 2009 13:32:57 -0500<br>> To:<span class="ecxApple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>> CC:<span class="ecxApple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>> Subject: Re: [M3devel] cas/casp?<br>><span class="ecxApple-converted-space"> </span><br>> Hold your horses. I am in the middle of working up a more portable "Atomic" interface along the following lines. We can choose to implement with compiler intrinsics like Word/LongWord (if available), but otherwise will provide a call interface. I envision instantiating for ADDRESS, CHAR, and Word.T. This means CAS/CASP will go away.<br>><span class="ecxApple-converted-space"> </span><br>> GENERIC INTERFACE Atomic(Rep);<br>><span class="ecxApple-converted-space"> </span><br>> IMPORT RTMachine;<br>><span class="ecxApple-converted-space"> </span><br>> TYPE T = Rep.T;<br>><span class="ecxApple-converted-space"> </span><br>> PROCEDURE MemoryFence();<br>> (* Guarantees explicit memory ordering for otherwise unordered atomics, and<br>> for other memory references wrt atomics. Not useful for ordering<br>> ordinary memory references, since those may not race and, if they don't<br>> race, always appear to be ordered. *)<br>><span class="ecxApple-converted-space"> </span><br>> PROCEDURE CompilerFence();<br>> (* Ensures that prior memory operations appear in the instruction stream<br>> before subsequent ones, i.e. the compiler is not allowed to reorder<br>> around this. This really has only implementation-defined semantics, but<br>> it seems to be useful in ensuring ordering with respect to signal<br>> handlers and the like. *)<br>><span class="ecxApple-converted-space"> </span><br>> PROCEDURE Store(VAR var: T; val: T); (* No ordering guarantees. *)<br>> PROCEDURE StoreRelease(VAR var: T; val: T);<br>><span class="ecxApple-converted-space"> </span><br>> PROCEDURE Load(READONLY var: T): T; (* No ordering guarantees. *)<br>> PROCEDURE LoadAcquire(READONLY var: T): T;<br>><span class="ecxApple-converted-space"> </span><br>> TYPE Order = { Raw, Acquire, Release, Ordered };<br>> (* "Raw" ==> This operation is unordered, and may become visible to other<br>> threads in an order that is constrained only by ordering constraints<br>> on other operations.<br>><span class="ecxApple-converted-space"> </span><br>> "Release" ==> All prior memory operations (including ordinary<br>> assignments) become visible to a an acquire operation on the same<br>> object that sees the resulting value.<br>><span class="ecxApple-converted-space"> </span><br>> "Acquire" ==> See above.<br>><span class="ecxApple-converted-space"> </span><br>> "Ordered" ==> Both acquire and release ordering properties.*)<br>><span class="ecxApple-converted-space"> </span><br>> CONST HasCas = RTMachine.HasCas;<br>> CONST HasWaitFreeCas = RTMachine.HasWaitFreeCas;<br>> PROCEDURE Cas(VAR var: T; old, new: T; order := Ordered): T;<br>> (* Most architectures provide a way to return the old value. On those that<br>> do not, it can be emulated with an additional load, at the expense of<br>> wait-freedom or spurious failure. *)<br>><span class="ecxApple-converted-space"> </span><br>> CONST HasWeakCas = RTMachine.HasWeakCas;<br>> PROCEDURE WeakCas(VAR var: T; old, new: T; order := Ordered): T;<br>> (* Similar to "Cas", but may fail spuriously, and must be wait-free, if<br>> provided. *)<br>><span class="ecxApple-converted-space"> </span><br>> CONST HasFetchAdd = RTMachine.HasFetchAdd;<br>> PROCEDURE FetchAdd(VAR var; incr: T; order := Raw): T;<br>><span class="ecxApple-converted-space"> </span><br>> CONST HasFetchOr = RTMachine.HasFetchOr;<br>> PROCEDURE FetchOr(VAR var; mask: T; order := Raw): T;<br>><span class="ecxApple-converted-space"> </span><br>> CONST HasFetchAnd = RTMachine.HasFetchAnd;<br>> PROCEDURE FetchOr(VAR var; mask: T; order := Raw): T;<br>><span class="ecxApple-converted-space"> </span><br>> END Atomic.<br>><span class="ecxApple-converted-space"> </span><br>><span class="ecxApple-converted-space"> </span><br>> On 18 Dec 2009, at 13:04, Jay K wrote:<br>><span class="ecxApple-converted-space"> </span><br>> > Tony is this right?<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > conceptually:<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > result := CAS(VAR destination, compare, exchange)<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > old := destination<br>> > if old := compare then<br>> > destination = exchange<br>> > return old<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > bool result := CASP(VAR destination, compare, exchange)<br>> > P for predicate aka returning bool<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > old := destination<br>> > if old = compare then<br>> > destination := exchange<br>> > return true<br>> > return false<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > I'm pretty sure it is.<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > I'll have this for 16 bit and 32 bit values shortly, for now requiring<br>> > a recent Microsoft compiler and it generates function calls.<br>> > But inlining should be easy enough.<br>> > And then 8bit and 64bit.<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > Also this will probably not work on 386 or 486 but require Pentium or somesuch.<br>> > I don't know when various instructions were introduced but I know<br>> > 386 is much poorer here than modern processors.<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > I assume only support int8, uint8, int16, uint16, int32, uint32, int64, uint64, size_t, ptrdiff_t<br>> > and not e.g. floating point.<br>> ><span class="ecxApple-converted-space"> </span><br>> ><span class="ecxApple-converted-space"> </span><br>> > - Jay<br>><span class="ecxApple-converted-space"> </span><br></div></blockquote></div><br></div></span><br class="Apple-interchange-newline"></blockquote></div><br></body></html>