Mercurial > projects > ldc

comparison tango/tango/core/Atomic.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
1 /**
2 * The atomic module is intended to provide some basic support for lock-free
3 * concurrent programming. Some common operations are defined, each of which
4 * may be performed using the specified memory barrier or a less granular
5 * barrier if the hardware does not support the version requested. This
6 * model is based on a design by Alexander Terekhov as outlined in
7 * <a href=http://groups.google.com/groups?threadm=3E4820EE.6F408B25%40web.de>
8 * this thread</a>. Another useful reference for memory ordering on modern
9 * architectures is <a href=http://www.linuxjournal.com/article/8211>this
10 * article by Paul McKenney</a>.
11 *
12 * Copyright: Copyright (C) 2005-2006 Sean Kelly. All rights reserved.
13 * License: BSD style: $(LICENSE)
14 * Authors: Sean Kelly
15 */
16 module tango.core.Atomic;
17
18
19 ////////////////////////////////////////////////////////////////////////////////
20 // Synchronization Options
21 ////////////////////////////////////////////////////////////////////////////////
22
23
24 /**
25 * Memory synchronization flag. If the supplied option is not available on the
26 * current platform then a stronger method will be used instead.
27 */
28 enum msync
29 {
30 raw, /// not sequenced
31 hlb, /// hoist-load barrier
32 hsb, /// hoist-store barrier
33 slb, /// sink-load barrier
34 ssb, /// sink-store barrier
35 acq, /// hoist-load + hoist-store barrier
36 rel, /// sink-load + sink-store barrier
37 seq, /// fully sequenced (acq + rel)
38 }
39
40
41 ////////////////////////////////////////////////////////////////////////////////
42 // Internal Type Checking
43 ////////////////////////////////////////////////////////////////////////////////
44
45
46 private
47 {
48 version( DDoc ) {} else
49 {
50 import tango.core.Traits;
51
52
53 template isValidAtomicType( T )
54 {
55 const bool isValidAtomicType = T.sizeof == byte.sizeof ||
56 T.sizeof == short.sizeof ||
57 T.sizeof == int.sizeof ||
58 T.sizeof == long.sizeof;
59 }
60
61
62 template isValidNumericType( T )
63 {
64 const bool isValidNumericType = isIntegerType!( T ) ||
65 isPointerType!( T );
66 }
67
68
69 template isHoistOp( msync ms )
70 {
71 const bool isHoistOp = ms == msync.hlb ||
72 ms == msync.hsb ||
73 ms == msync.acq ||
74 ms == msync.seq;
75 }
76
77
78 template isSinkOp( msync ms )
79 {
80 const bool isSinkOp = ms == msync.slb ||
81 ms == msync.ssb ||
82 ms == msync.rel ||
83 ms == msync.seq;
84 }
85 }
86 }
87
88
89 ////////////////////////////////////////////////////////////////////////////////
90 // DDoc Documentation for Atomic Functions
91 ////////////////////////////////////////////////////////////////////////////////
92
93
94 version( DDoc )
95 {
96 ////////////////////////////////////////////////////////////////////////////
97 // Atomic Load
98 ////////////////////////////////////////////////////////////////////////////
99
100
101 /**
102 * Supported msync values:
103 * msync.raw
104 * msync.hlb
105 * msync.acq
106 * msync.seq
107 */
108 template atomicLoad( msync ms, T )
109 {
110 /**
111 * Refreshes the contents of 'val' from main memory. This operation is
112 * both lock-free and atomic.
113 *
114 * Params:
115 * val = The value to load. This value must be properly aligned.
116 *
117 * Returns:
118 * The loaded value.
119 */
120 T atomicLoad( inout T val )
121 {
122 return val;
123 }
124 }
125
126
127 ////////////////////////////////////////////////////////////////////////////
128 // Atomic Store
129 ////////////////////////////////////////////////////////////////////////////
130
131
132 /**
133 * Supported msync values:
134 * msync.raw
135 * msync.ssb
136 * msync.acq
137 * msync.rel
138 * msync.seq
139 */
140 template atomicStore( msync ms, T )
141 {
142 /**
143 * Stores 'newval' to the memory referenced by 'val'. This operation
144 * is both lock-free and atomic.
145 *
146 * Params:
147 * val = The destination variable.
148 * newval = The value to store.
149 */
150 void atomicStore( inout T val, T newval )
151 {
152
153 }
154 }
155
156
157 ////////////////////////////////////////////////////////////////////////////
158 // Atomic StoreIf
159 ////////////////////////////////////////////////////////////////////////////
160
161
162 /**
163 * Supported msync values:
164 * msync.raw
165 * msync.ssb
166 * msync.acq
167 * msync.rel
168 * msync.seq
169 */
170 template atomicStoreIf( msync ms, T )
171 {
172 /**
173 * Stores 'newval' to the memory referenced by 'val' if val is equal to
174 * 'equalTo'. This operation is both lock-free and atomic.
175 *
176 * Params:
177 * val = The destination variable.
178 * newval = The value to store.
179 * equalTo = The comparison value.
180 *
181 * Returns:
182 * true if the store occurred, false if not.
183 */
184 bool atomicStoreIf( inout T val, T newval, T equalTo )
185 {
186 return false;
187 }
188 }
189
190
191 ////////////////////////////////////////////////////////////////////////////
192 // Atomic Increment
193 ////////////////////////////////////////////////////////////////////////////
194
195
196 /**
197 * Supported msync values:
198 * msync.raw
199 * msync.ssb
200 * msync.acq
201 * msync.rel
202 * msync.seq
203 */
204 template atomicIncrement( msync ms, T )
205 {
206 /**
207 * This operation is only legal for built-in value and pointer types,
208 * and is equivalent to an atomic "val = val + 1" operation. This
209 * function exists to facilitate use of the optimized increment
210 * instructions provided by some architecures. If no such instruction
211 * exists on the target platform then the behavior will perform the
212 * operation using more traditional means. This operation is both
213 * lock-free and atomic.
214 *
215 * Params:
216 * val = The value to increment.
217 *
218 * Returns:
219 * The result of an atomicLoad of val immediately following the
220 * increment operation. This value is not required to be equal to the
221 * newly stored value. Thus, competing writes are allowed to occur
222 * between the increment and successive load operation.
223 */
224 T atomicIncrement( inout T val )
225 {
226 return val;
227 }
228 }
229
230
231 ////////////////////////////////////////////////////////////////////////////
232 // Atomic Decrement
233 ////////////////////////////////////////////////////////////////////////////
234
235
236 /**
237 * Supported msync values:
238 * msync.raw
239 * msync.ssb
240 * msync.acq
241 * msync.rel
242 * msync.seq
243 */
244 template atomicDecrement( msync ms, T )
245 {
246 /**
247 * This operation is only legal for built-in value and pointer types,
248 * and is equivalent to an atomic "val = val - 1" operation. This
249 * function exists to facilitate use of the optimized decrement
250 * instructions provided by some architecures. If no such instruction
251 * exists on the target platform then the behavior will perform the
252 * operation using more traditional means. This operation is both
253 * lock-free and atomic.
254 *
255 * Params:
256 * val = The value to decrement.
257 *
258 * Returns:
259 * The result of an atomicLoad of val immediately following the
260 * increment operation. This value is not required to be equal to the
261 * newly stored value. Thus, competing writes are allowed to occur
262 * between the increment and successive load operation.
263 */
264 T atomicDecrement( inout T val )
265 {
266 return val;
267 }
268 }
269 }
270
271
272 ////////////////////////////////////////////////////////////////////////////////
273 // x86 Atomic Function Implementation
274 ////////////////////////////////////////////////////////////////////////////////
275
276
277 else version( D_InlineAsm_X86 )
278 {
279 version( X86 )
280 {
281 version( BuildInfo )
282 {
283 pragma( msg, "tango.core.Atomic: using IA-32 inline asm" );
284 }
285
286 version = Has32BitOps;
287 version = Has64BitCAS;
288 }
289 version( X86_64 )
290 {
291 version( BuildInfo )
292 {
293 pragma( msg, "tango.core.Atomic: using AMD64 inline asm" );
294 }
295
296 version = Has64BitOps;
297 }
298
299 private
300 {
301 ////////////////////////////////////////////////////////////////////////
302 // x86 Value Requirements
303 ////////////////////////////////////////////////////////////////////////
304
305
306 // NOTE: Strictly speaking, the x86 supports atomic operations on
307 // unaligned values. However, this is far slower than the
308 // common case, so such behavior should be prohibited.
309 template atomicValueIsProperlyAligned( T )
310 {
311 bool atomicValueIsProperlyAligned( size_t addr )
312 {
313 return addr % T.sizeof == 0;
314 }
315 }
316
317
318 ////////////////////////////////////////////////////////////////////////
319 // x86 Synchronization Requirements
320 ////////////////////////////////////////////////////////////////////////
321
322
323 // NOTE: While x86 loads have acquire semantics for stores, it appears
324 // that independent loads may be reordered by some processors
325 // (notably the AMD64). This implies that the hoist-load barrier
326 // op requires an ordering instruction, which also extends this
327 // requirement to acquire ops (though hoist-store should not need
328 // one if support is added for this later). However, since no
329 // modern architectures will reorder dependent loads to occur
330 // before the load they depend on (except the Alpha), raw loads
331 // are actually a possible means of ordering specific sequences
332 // of loads in some instances. The original atomic<>
333 // implementation provides a 'ddhlb' ordering specifier for
334 // data-dependent loads to handle this situation, but as there
335 // are no plans to support the Alpha there is no reason to add
336 // that option here.
337 //
338 // For reference, the old behavior (acquire semantics for loads)
339 // required a memory barrier if: ms == msync.seq || isSinkOp!(ms)
340 template needsLoadBarrier( msync ms )
341 {
342 const bool needsLoadBarrier = ms != msync.raw;
343 }
344
345
346 // NOTE: x86 stores implicitly have release semantics so a membar is only
347 // necessary on acquires.
348 template needsStoreBarrier( msync ms )
349 {
350 const bool needsStoreBarrier = ms == msync.seq || isHoistOp!(ms);
351 }
352 }
353
354
355 ////////////////////////////////////////////////////////////////////////////
356 // Atomic Load
357 ////////////////////////////////////////////////////////////////////////////
358
359
360 template atomicLoad( msync ms = msync.seq, T )
361 {
362 T atomicLoad( inout T val )
363 in
364 {
365 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
366 }
367 body
368 {
369 static if( T.sizeof == byte.sizeof )
370 {
371 ////////////////////////////////////////////////////////////////
372 // 1 Byte Load
373 ////////////////////////////////////////////////////////////////
374
375
376 static if( needsLoadBarrier!(ms) )
377 {
378 volatile asm
379 {
380 mov BL, 42;
381 mov AL, 42;
382 mov ECX, val;
383 lock;
384 cmpxchg [ECX], BL;
385 }
386 }
387 else
388 {
389 volatile
390 {
391 return val;
392 }
393 }
394 }
395 else static if( T.sizeof == short.sizeof )
396 {
397 ////////////////////////////////////////////////////////////////
398 // 2 Byte Load
399 ////////////////////////////////////////////////////////////////
400
401 static if( needsLoadBarrier!(ms) )
402 {
403 volatile asm
404 {
405 mov BX, 42;
406 mov AX, 42;
407 mov ECX, val;
408 lock;
409 cmpxchg [ECX], BX;
410 }
411 }
412 else
413 {
414 volatile
415 {
416 return val;
417 }
418 }
419 }
420 else static if( T.sizeof == int.sizeof )
421 {
422 ////////////////////////////////////////////////////////////////
423 // 4 Byte Load
424 ////////////////////////////////////////////////////////////////
425
426
427 static if( needsLoadBarrier!(ms) )
428 {
429 volatile asm
430 {
431 mov EBX, 42;
432 mov EAX, 42;
433 mov ECX, val;
434 lock;
435 cmpxchg [ECX], EBX;
436 }
437 }
438 else
439 {
440 volatile
441 {
442 return val;
443 }
444 }
445 }
446 else static if( T.sizeof == long.sizeof )
447 {
448 ////////////////////////////////////////////////////////////////
449 // 8 Byte Load
450 ////////////////////////////////////////////////////////////////
451
452
453 version( Has64BitOps )
454 {
455 ////////////////////////////////////////////////////////////
456 // 8 Byte Load on 64-Bit Processor
457 ////////////////////////////////////////////////////////////
458
459
460 static if( needsLoadBarrier!(ms) )
461 {
462 volatile asm
463 {
464 mov RAX, val;
465 lock;
466 mov RAX, [RAX];
467 }
468 }
469 else
470 {
471 volatile
472 {
473 return val;
474 }
475 }
476 }
477 else
478 {
479 ////////////////////////////////////////////////////////////
480 // 8 Byte Load on 32-Bit Processor
481 ////////////////////////////////////////////////////////////
482
483
484 pragma( msg, "This operation is only available on 64-bit platforms." );
485 static assert( false );
486 }
487 }
488 else
489 {
490 ////////////////////////////////////////////////////////////////
491 // Not a 1, 2, 4, or 8 Byte Type
492 ////////////////////////////////////////////////////////////////
493
494
495 pragma( msg, "Invalid template type specified." );
496 static assert( false );
497 }
498 }
499 }
500
501
502 ////////////////////////////////////////////////////////////////////////////
503 // Atomic Store
504 ////////////////////////////////////////////////////////////////////////////
505
506
507 template atomicStore( msync ms = msync.seq, T )
508 {
509 void atomicStore( inout T val, T newval )
510 in
511 {
512 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
513 }
514 body
515 {
516 static if( T.sizeof == byte.sizeof )
517 {
518 ////////////////////////////////////////////////////////////////
519 // 1 Byte Store
520 ////////////////////////////////////////////////////////////////
521
522
523 static if( needsStoreBarrier!(ms) )
524 {
525 volatile asm
526 {
527 mov EAX, val;
528 mov BL, newval;
529 lock;
530 xchg [EAX], BL;
531 }
532 }
533 else
534 {
535 volatile asm
536 {
537 mov EAX, val;
538 mov BL, newval;
539 mov [EAX], BL;
540 }
541 }
542 }
543 else static if( T.sizeof == short.sizeof )
544 {
545 ////////////////////////////////////////////////////////////////
546 // 2 Byte Store
547 ////////////////////////////////////////////////////////////////
548
549
550 static if( needsStoreBarrier!(ms) )
551 {
552 volatile asm
553 {
554 mov EAX, val;
555 mov BX, newval;
556 lock;
557 xchg [EAX], BX;
558 }
559 }
560 else
561 {
562 volatile asm
563 {
564 mov EAX, val;
565 mov BX, newval;
566 mov [EAX], BX;
567 }
568 }
569 }
570 else static if( T.sizeof == int.sizeof )
571 {
572 ////////////////////////////////////////////////////////////////
573 // 4 Byte Store
574 ////////////////////////////////////////////////////////////////
575
576
577 static if( needsStoreBarrier!(ms) )
578 {
579 volatile asm
580 {
581 mov EAX, val;
582 mov EBX, newval;
583 lock;
584 xchg [EAX], EBX;
585 }
586 }
587 else
588 {
589 volatile asm
590 {
591 mov EAX, val;
592 mov EBX, newval;
593 mov [EAX], EBX;
594 }
595 }
596 }
597 else static if( T.sizeof == long.sizeof )
598 {
599 ////////////////////////////////////////////////////////////////
600 // 8 Byte Store
601 ////////////////////////////////////////////////////////////////
602
603
604 version( Has64BitOps )
605 {
606 ////////////////////////////////////////////////////////////
607 // 8 Byte Store on 64-Bit Processor
608 ////////////////////////////////////////////////////////////
609
610
611 static if( needsStoreBarrier!(ms) )
612 {
613 volatile asm
614 {
615 mov RAX, val;
616 mov RBX, newval;
617 lock;
618 xchg [RAX], RBX;
619 }
620 }
621 else
622 {
623 volatile asm
624 {
625 mov RAX, val;
626 mov RBX, newval;
627 mov [RAX], RBX;
628 }
629 }
630 }
631 else
632 {
633 ////////////////////////////////////////////////////////////
634 // 8 Byte Store on 32-Bit Processor
635 ////////////////////////////////////////////////////////////
636
637
638 pragma( msg, "This operation is only available on 64-bit platforms." );
639 static assert( false );
640 }
641 }
642 else
643 {
644 ////////////////////////////////////////////////////////////////
645 // Not a 1, 2, 4, or 8 Byte Type
646 ////////////////////////////////////////////////////////////////
647
648
649 pragma( msg, "Invalid template type specified." );
650 static assert( false );
651 }
652 }
653 }
654
655
656 ////////////////////////////////////////////////////////////////////////////
657 // Atomic Store If
658 ////////////////////////////////////////////////////////////////////////////
659
660
661 template atomicStoreIf( msync ms = msync.seq, T )
662 {
663 bool atomicStoreIf( inout T val, T newval, T equalTo )
664 in
665 {
666 // NOTE: 32 bit x86 systems support 8 byte CAS, which only requires
667 // 4 byte alignment, so use size_t as the align type here.
668 static if( T.sizeof > size_t.sizeof )
669 assert( atomicValueIsProperlyAligned!(size_t)( cast(size_t) &val ) );
670 else
671 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
672 }
673 body
674 {
675 static if( T.sizeof == byte.sizeof )
676 {
677 ////////////////////////////////////////////////////////////////
678 // 1 Byte StoreIf
679 ////////////////////////////////////////////////////////////////
680
681
682 volatile asm
683 {
684 mov BL, newval;
685 mov AL, equalTo;
686 mov ECX, val;
687 lock; // lock always needed to make this op atomic
688 cmpxchg [ECX], BL;
689 setz AL;
690 }
691 }
692 else static if( T.sizeof == short.sizeof )
693 {
694 ////////////////////////////////////////////////////////////////
695 // 2 Byte StoreIf
696 ////////////////////////////////////////////////////////////////
697
698
699 volatile asm
700 {
701 mov BX, newval;
702 mov AX, equalTo;
703 mov ECX, val;
704 lock; // lock always needed to make this op atomic
705 cmpxchg [ECX], BX;
706 setz AL;
707 }
708 }
709 else static if( T.sizeof == int.sizeof )
710 {
711 ////////////////////////////////////////////////////////////////
712 // 4 Byte StoreIf
713 ////////////////////////////////////////////////////////////////
714
715
716 volatile asm
717 {
718 mov EBX, newval;
719 mov EAX, equalTo;
720 mov ECX, val;
721 lock; // lock always needed to make this op atomic
722 cmpxchg [ECX], EBX;
723 setz AL;
724 }
725 }
726 else static if( T.sizeof == long.sizeof )
727 {
728 ////////////////////////////////////////////////////////////////
729 // 8 Byte StoreIf
730 ////////////////////////////////////////////////////////////////
731
732
733 version( Has64BitOps )
734 {
735 ////////////////////////////////////////////////////////////
736 // 8 Byte StoreIf on 64-Bit Processor
737 ////////////////////////////////////////////////////////////
738
739
740 volatile asm
741 {
742 mov RBX, newval;
743 mov RAX, equalTo;
744 mov RCX, val;
745 lock; // lock always needed to make this op atomic
746 cmpxchg [RCX], RBX;
747 setz AL;
748 }
749 }
750 else version( Has64BitCAS )
751 {
752 ////////////////////////////////////////////////////////////
753 // 8 Byte StoreIf on 32-Bit Processor
754 ////////////////////////////////////////////////////////////
755
756
757 volatile asm
758 {
759 lea EDI, newval;
760 mov EBX, [EDI];
761 mov ECX, 4[EDI];
762 lea EDI, equalTo;
763 mov EAX, [EDI];
764 mov EDX, 4[EDI];
765 mov EDI, val;
766 lock; // lock always needed to make this op atomic
767 cmpxch8b [EDI];
768 setz AL;
769 }
770 }
771 }
772 else
773 {
774 ////////////////////////////////////////////////////////////////
775 // Not a 1, 2, 4, or 8 Byte Type
776 ////////////////////////////////////////////////////////////////
777
778
779 pragma( msg, "Invalid template type specified." );
780 static assert( false );
781 }
782 }
783 }
784
785
786 ////////////////////////////////////////////////////////////////////////////
787 // Atomic Increment
788 ////////////////////////////////////////////////////////////////////////////
789
790
791 template atomicIncrement( msync ms = msync.seq, T )
792 {
793 //
794 // NOTE: This operation is only valid for integer or pointer types
795 //
796 static assert( isValidNumericType!(T) );
797
798
799 T atomicIncrement( inout T val )
800 in
801 {
802 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
803 }
804 body
805 {
806 static if( T.sizeof == byte.sizeof )
807 {
808 ////////////////////////////////////////////////////////////////
809 // 1 Byte Increment
810 ////////////////////////////////////////////////////////////////
811
812
813 volatile asm
814 {
815 mov EAX, val;
816 lock; // lock always needed to make this op atomic
817 inc [EAX];
818 mov AL, [EAX];
819 }
820 }
821 else static if( T.sizeof == short.sizeof )
822 {
823 ////////////////////////////////////////////////////////////////
824 // 2 Byte Increment
825 ////////////////////////////////////////////////////////////////
826
827
828 volatile asm
829 {
830 mov EAX, val;
831 lock; // lock always needed to make this op atomic
832 inc [EAX];
833 mov AX, [EAX];
834 }
835 }
836 else static if( T.sizeof == int.sizeof )
837 {
838 ////////////////////////////////////////////////////////////////
839 // 4 Byte Increment
840 ////////////////////////////////////////////////////////////////
841
842
843 volatile asm
844 {
845 mov EAX, val;
846 lock; // lock always needed to make this op atomic
847 inc [EAX];
848 mov EAX, [EAX];
849 }
850 }
851 else static if( T.sizeof == long.sizeof )
852 {
853 ////////////////////////////////////////////////////////////////
854 // 8 Byte Increment
855 ////////////////////////////////////////////////////////////////
856
857
858 version( Has64BitOps )
859 {
860 ////////////////////////////////////////////////////////////
861 // 8 Byte Increment on 64-Bit Processor
862 ////////////////////////////////////////////////////////////
863
864
865 volatile asm
866 {
867 mov RAX, val;
868 lock; // lock always needed to make this op atomic
869 inc [RAX];
870 mov RAX, [RAX];
871 }
872 }
873 else
874 {
875 ////////////////////////////////////////////////////////////
876 // 8 Byte Increment on 32-Bit Processor
877 ////////////////////////////////////////////////////////////
878
879
880 pragma( msg, "This operation is only available on 64-bit platforms." );
881 static assert( false );
882 }
883 }
884 else
885 {
886 ////////////////////////////////////////////////////////////////
887 // Not a 1, 2, 4, or 8 Byte Type
888 ////////////////////////////////////////////////////////////////
889
890
891 pragma( msg, "Invalid template type specified." );
892 static assert( false );
893 }
894 }
895 }
896
897
898 ////////////////////////////////////////////////////////////////////////////
899 // Atomic Decrement
900 ////////////////////////////////////////////////////////////////////////////
901
902
903 template atomicDecrement( msync ms = msync.seq, T )
904 {
905 //
906 // NOTE: This operation is only valid for integer or pointer types
907 //
908 static assert( isValidNumericType!(T) );
909
910
911 T atomicDecrement( inout T val )
912 in
913 {
914 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
915 }
916 body
917 {
918 static if( T.sizeof == byte.sizeof )
919 {
920 ////////////////////////////////////////////////////////////////
921 // 1 Byte Decrement
922 ////////////////////////////////////////////////////////////////
923
924
925 volatile asm
926 {
927 mov EAX, val;
928 lock; // lock always needed to make this op atomic
929 dec [EAX];
930 mov AL, [EAX];
931 }
932 }
933 else static if( T.sizeof == short.sizeof )
934 {
935 ////////////////////////////////////////////////////////////////
936 // 2 Byte Decrement
937 ////////////////////////////////////////////////////////////////
938
939
940 volatile asm
941 {
942 mov EAX, val;
943 lock; // lock always needed to make this op atomic
944 dec [EAX];
945 mov AX, [EAX];
946 }
947 }
948 else static if( T.sizeof == int.sizeof )
949 {
950 ////////////////////////////////////////////////////////////////
951 // 4 Byte Decrement
952 ////////////////////////////////////////////////////////////////
953
954
955 volatile asm
956 {
957 mov EAX, val;
958 lock; // lock always needed to make this op atomic
959 dec [EAX];
960 mov EAX, [EAX];
961 }
962 }
963 else static if( T.sizeof == long.sizeof )
964 {
965 ////////////////////////////////////////////////////////////////
966 // 8 Byte Decrement
967 ////////////////////////////////////////////////////////////////
968
969
970 version( Has64BitOps )
971 {
972 ////////////////////////////////////////////////////////////
973 // 8 Byte Decrement on 64-Bit Processor
974 ////////////////////////////////////////////////////////////
975
976
977 volatile asm
978 {
979 mov RAX, val;
980 lock; // lock always needed to make this op atomic
981 dec [RAX];
982 mov RAX, [RAX];
983 }
984 }
985 else
986 {
987 ////////////////////////////////////////////////////////////
988 // 8 Byte Decrement on 32-Bit Processor
989 ////////////////////////////////////////////////////////////
990
991
992 pragma( msg, "This operation is only available on 64-bit platforms." );
993 static assert( false );
994 }
995 }
996 else
997 {
998 ////////////////////////////////////////////////////////////////
999 // Not a 1, 2, 4, or 8 Byte Type
1000 ////////////////////////////////////////////////////////////////
1001
1002
1003 pragma( msg, "Invalid template type specified." );
1004 static assert( false );
1005 }
1006 }
1007 }
1008 }
1009 else
1010 {
1011 version( BuildInfo )
1012 {
1013 pragma( msg, "tango.core.Atomic: using synchronized ops" );
1014 }
1015
1016 private
1017 {
1018 ////////////////////////////////////////////////////////////////////////
1019 // Default Value Requirements
1020 ////////////////////////////////////////////////////////////////////////
1021
1022
1023 template atomicValueIsProperlyAligned( T )
1024 {
1025 bool atomicValueIsProperlyAligned( size_t addr )
1026 {
1027 return addr % T.sizeof == 0;
1028 }
1029 }
1030
1031
1032 ////////////////////////////////////////////////////////////////////////
1033 // Default Synchronization Requirements
1034 ////////////////////////////////////////////////////////////////////////
1035
1036
1037 template needsLoadBarrier( msync ms )
1038 {
1039 const bool needsLoadBarrier = ms != msync.raw;
1040 }
1041
1042
1043 template needsStoreBarrier( msync ms )
1044 {
1045 const bool needsStoreBarrier = ms != msync.raw;
1046 }
1047 }
1048
1049
1050 ////////////////////////////////////////////////////////////////////////////
1051 // Atomic Load
1052 ////////////////////////////////////////////////////////////////////////////
1053
1054
1055 template atomicLoad( msync ms = msync.seq, T )
1056 {
1057 T atomicLoad( inout T val )
1058 in
1059 {
1060 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
1061 }
1062 body
1063 {
1064 static if( T.sizeof <= (void*).sizeof )
1065 {
1066 ////////////////////////////////////////////////////////////////
1067 // <= (void*).sizeof Byte Load
1068 ////////////////////////////////////////////////////////////////
1069
1070
1071 static if( needsLoadBarrier!(ms) )
1072 {
1073 synchronized
1074 {
1075 return val;
1076 }
1077 }
1078 else
1079 {
1080 volatile
1081 {
1082 return val;
1083 }
1084 }
1085 }
1086 else
1087 {
1088 ////////////////////////////////////////////////////////////////
1089 // > (void*).sizeof Byte Type
1090 ////////////////////////////////////////////////////////////////
1091
1092
1093 pragma( msg, "Invalid template type specified." );
1094 static assert( false );
1095 }
1096 }
1097 }
1098
1099
1100 ////////////////////////////////////////////////////////////////////////////
1101 // Atomic Store
1102 ////////////////////////////////////////////////////////////////////////////
1103
1104
1105 template atomicStore( msync ms = msync.seq, T )
1106 {
1107 void atomicStore( inout T val, T newval )
1108 in
1109 {
1110 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
1111 }
1112 body
1113 {
1114 static if( T.sizeof <= (void*).sizeof )
1115 {
1116 ////////////////////////////////////////////////////////////////
1117 // <= (void*).sizeof Byte Store
1118 ////////////////////////////////////////////////////////////////
1119
1120
1121 static if( needsStoreBarrier!(ms) )
1122 {
1123 synchronized
1124 {
1125 val = newval;
1126 }
1127 }
1128 else
1129 {
1130 volatile
1131 {
1132 val = newval;
1133 }
1134 }
1135 }
1136 else
1137 {
1138 ////////////////////////////////////////////////////////////////
1139 // > (void*).sizeof Byte Type
1140 ////////////////////////////////////////////////////////////////
1141
1142
1143 pragma( msg, "Invalid template type specified." );
1144 static assert( false );
1145 }
1146 }
1147 }
1148
1149
1150 ////////////////////////////////////////////////////////////////////////////
1151 // Atomic Store If
1152 ////////////////////////////////////////////////////////////////////////////
1153
1154
1155 template atomicStoreIf( msync ms = msync.seq, T )
1156 {
1157 bool atomicStoreIf( inout T val, T newval, T equalTo )
1158 in
1159 {
1160 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
1161 }
1162 body
1163 {
1164 static if( T.sizeof <= (void*).sizeof )
1165 {
1166 ////////////////////////////////////////////////////////////////
1167 // <= (void*).sizeof Byte StoreIf
1168 ////////////////////////////////////////////////////////////////
1169
1170
1171 synchronized
1172 {
1173 if( val == equalTo )
1174 {
1175 val = newval;
1176 return true;
1177 }
1178 return false;
1179 }
1180 }
1181 else
1182 {
1183 ////////////////////////////////////////////////////////////////
1184 // > (void*).sizeof Byte Type
1185 ////////////////////////////////////////////////////////////////
1186
1187
1188 pragma( msg, "Invalid template type specified." );
1189 static assert( false );
1190 }
1191 }
1192 }
1193
1194
1195 /////////////////////////////////////////////////////////////////////////////
1196 // Atomic Increment
1197 ////////////////////////////////////////////////////////////////////////////
1198
1199
1200 template atomicIncrement( msync ms = msync.seq, T )
1201 {
1202 //
1203 // NOTE: This operation is only valid for integer or pointer types
1204 //
1205 static assert( isValidNumericType!(T) );
1206
1207
1208 T atomicIncrement( inout T val )
1209 in
1210 {
1211 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
1212 }
1213 body
1214 {
1215 static if( T.sizeof <= (void*).sizeof )
1216 {
1217 ////////////////////////////////////////////////////////////////
1218 // <= (void*).sizeof Byte Increment
1219 ////////////////////////////////////////////////////////////////
1220
1221
1222 synchronized
1223 {
1224 return ++val;
1225 }
1226 }
1227 else
1228 {
1229 ////////////////////////////////////////////////////////////////
1230 // > (void*).sizeof Byte Type
1231 ////////////////////////////////////////////////////////////////
1232
1233
1234 pragma( msg, "Invalid template type specified." );
1235 static assert( false );
1236 }
1237 }
1238 }
1239
1240
1241 ////////////////////////////////////////////////////////////////////////////
1242 // Atomic Decrement
1243 ////////////////////////////////////////////////////////////////////////////
1244
1245
1246 template atomicDecrement( msync ms = msync.seq, T )
1247 {
1248 //
1249 // NOTE: This operation is only valid for integer or pointer types
1250 //
1251 static assert( isValidNumericType!(T) );
1252
1253
1254 T atomicDecrement( inout T val )
1255 in
1256 {
1257 assert( atomicValueIsProperlyAligned!(T)( cast(size_t) &val ) );
1258 }
1259 body
1260 {
1261 static if( T.sizeof <= (void*).sizeof )
1262 {
1263 ////////////////////////////////////////////////////////////////
1264 // <= (void*).sizeof Byte Decrement
1265 ////////////////////////////////////////////////////////////////
1266
1267
1268 synchronized
1269 {
1270 return --val;
1271 }
1272 }
1273 else
1274 {
1275 ////////////////////////////////////////////////////////////////
1276 // > (void*).sizeof Byte Type
1277 ////////////////////////////////////////////////////////////////
1278
1279
1280 pragma( msg, "Invalid template type specified." );
1281 static assert( false );
1282 }
1283 }
1284 }
1285 }
1286
1287
1288 ////////////////////////////////////////////////////////////////////////////////
1289 // Atomic
1290 ////////////////////////////////////////////////////////////////////////////////
1291
1292
1293 /**
1294 * This struct represents a value which will be subject to competing access.
1295 * All accesses to this value will be synchronized with main memory, and
1296 * various memory barriers may be employed for instruction ordering. Any
1297 * primitive type of size equal to or smaller than the memory bus size is
1298 * allowed, so 32-bit machines may use values with size <= int.sizeof and
1299 * 64-bit machines may use values with size <= long.sizeof. The one exception
1300 * to this rule is that architectures that support DCAS will allow double-wide
1301 * storeIf operations. The 32-bit x86 architecture, for example, supports
1302 * 64-bit storeIf operations.
1303 */
1304 struct Atomic( T )
1305 {
1306 ////////////////////////////////////////////////////////////////////////////
1307 // Atomic Load
1308 ////////////////////////////////////////////////////////////////////////////
1309
1310
1311 template load( msync ms = msync.seq )
1312 {
1313 static assert( ms == msync.raw || ms == msync.hlb ||
1314 ms == msync.acq || ms == msync.seq,
1315 "ms must be one of: msync.raw, msync.hlb, msync.acq, msync.seq" );
1316
1317 /**
1318 * Refreshes the contents of this value from main memory. This
1319 * operation is both lock-free and atomic.
1320 *
1321 * Returns:
1322 * The loaded value.
1323 */
1324 T load()
1325 {
1326 return atomicLoad!(ms,T)( m_val );
1327 }
1328 }
1329
1330
1331 ////////////////////////////////////////////////////////////////////////////
1332 // Atomic Store
1333 ////////////////////////////////////////////////////////////////////////////
1334
1335
1336 template store( msync ms = msync.seq )
1337 {
1338 static assert( ms == msync.raw || ms == msync.ssb ||
1339 ms == msync.acq || ms == msync.rel ||
1340 ms == msync.seq,
1341 "ms must be one of: msync.raw, msync.ssb, msync.acq, msync.rel, msync.seq" );
1342
1343 /**
1344 * Stores 'newval' to the memory referenced by this value. This
1345 * operation is both lock-free and atomic.
1346 *
1347 * Params:
1348 * newval = The value to store.
1349 */
1350 void store( T newval )
1351 {
1352 atomicStore!(ms,T)( m_val, newval );
1353 }
1354 }
1355
1356
1357 ////////////////////////////////////////////////////////////////////////////
1358 // Atomic StoreIf
1359 ////////////////////////////////////////////////////////////////////////////
1360
1361
1362 template storeIf( msync ms = msync.seq )
1363 {
1364 static assert( ms == msync.raw || ms == msync.ssb ||
1365 ms == msync.acq || ms == msync.rel ||
1366 ms == msync.seq,
1367 "ms must be one of: msync.raw, msync.ssb, msync.acq, msync.rel, msync.seq" );
1368
1369 /**
1370 * Stores 'newval' to the memory referenced by this value if val is
1371 * equal to 'equalTo'. This operation is both lock-free and atomic.
1372 *
1373 * Params:
1374 * newval = The value to store.
1375 * equalTo = The comparison value.
1376 *
1377 * Returns:
1378 * true if the store occurred, false if not.
1379 */
1380 bool storeIf( T newval, T equalTo )
1381 {
1382 return atomicStoreIf!(ms,T)( m_val, newval, equalTo );
1383 }
1384 }
1385
1386
1387 ////////////////////////////////////////////////////////////////////////////
1388 // Numeric Functions
1389 ////////////////////////////////////////////////////////////////////////////
1390
1391
1392 /**
1393 * The following additional functions are available for integer types.
1394 */
1395 static if( isValidNumericType!(T) )
1396 {
1397 ////////////////////////////////////////////////////////////////////////
1398 // Atomic Increment
1399 ////////////////////////////////////////////////////////////////////////
1400
1401
1402 template increment( msync ms = msync.seq )
1403 {
1404 static assert( ms == msync.raw || ms == msync.ssb ||
1405 ms == msync.acq || ms == msync.rel ||
1406 ms == msync.seq,
1407 "ms must be one of: msync.raw, msync.ssb, msync.acq, msync.rel, msync.seq" );
1408
1409 /**
1410 * This operation is only legal for built-in value and pointer
1411 * types, and is equivalent to an atomic "val = val + 1" operation.
1412 * This function exists to facilitate use of the optimized
1413 * increment instructions provided by some architecures. If no
1414 * such instruction exists on the target platform then the
1415 * behavior will perform the operation using more traditional
1416 * means. This operation is both lock-free and atomic.
1417 *
1418 * Returns:
1419 * The result of an atomicLoad of val immediately following the
1420 * increment operation. This value is not required to be equal to
1421 * the newly stored value. Thus, competing writes are allowed to
1422 * occur between the increment and successive load operation.
1423 */
1424 T increment()
1425 {
1426 return atomicIncrement!(ms,T)( m_val );
1427 }
1428 }
1429
1430
1431 ////////////////////////////////////////////////////////////////////////
1432 // Atomic Decrement
1433 ////////////////////////////////////////////////////////////////////////
1434
1435
1436 template decrement( msync ms = msync.seq )
1437 {
1438 static assert( ms == msync.raw || ms == msync.ssb ||
1439 ms == msync.acq || ms == msync.rel ||
1440 ms == msync.seq,
1441 "ms must be one of: msync.raw, msync.ssb, msync.acq, msync.rel, msync.seq" );
1442
1443 /**
1444 * This operation is only legal for built-in value and pointer
1445 * types, and is equivalent to an atomic "val = val - 1" operation.
1446 * This function exists to facilitate use of the optimized
1447 * decrement instructions provided by some architecures. If no
1448 * such instruction exists on the target platform then the behavior
1449 * will perform the operation using more traditional means. This
1450 * operation is both lock-free and atomic.
1451 *
1452 * Returns:
1453 * The result of an atomicLoad of val immediately following the
1454 * increment operation. This value is not required to be equal to
1455 * the newly stored value. Thus, competing writes are allowed to
1456 * occur between the increment and successive load operation.
1457 */
1458 T decrement()
1459 {
1460 return atomicDecrement!(ms,T)( m_val );
1461 }
1462 }
1463 }
1464
1465 private:
1466 T m_val;
1467 }
1468
1469
1470 ////////////////////////////////////////////////////////////////////////////////
1471 // Support Code for Unit Tests
1472 ////////////////////////////////////////////////////////////////////////////////
1473
1474
1475 private
1476 {
1477 version( DDoc ) {} else
1478 {
1479 template testLoad( msync ms, T )
1480 {
1481 void testLoad( T val = T.init + 1 )
1482 {
1483 T base;
1484 Atomic!(T) atom;
1485
1486 assert( atom.load!(ms)() == base );
1487 base = val;
1488 atom.m_val = val;
1489 assert( atom.load!(ms)() == base );
1490 }
1491 }
1492
1493
1494 template testStore( msync ms, T )
1495 {
1496 void testStore( T val = T.init + 1 )
1497 {
1498 T base;
1499 Atomic!(T) atom;
1500
1501 assert( atom.m_val == base );
1502 base = val;
1503 atom.store!(ms)( base );
1504 assert( atom.m_val == base );
1505 }
1506 }
1507
1508
1509 template testStoreIf( msync ms, T )
1510 {
1511 void testStoreIf( T val = T.init + 1 )
1512 {
1513 T base;
1514 Atomic!(T) atom;
1515
1516 assert( atom.m_val == base );
1517 base = val;
1518 atom.storeIf!(ms)( base, val );
1519 assert( atom.m_val != base );
1520 atom.storeIf!(ms)( base, T.init );
1521 assert( atom.m_val == base );
1522 }
1523 }
1524
1525
1526 template testIncrement( msync ms, T )
1527 {
1528 void testIncrement( T val = T.init + 1 )
1529 {
1530 T base = val;
1531 T incr = val;
1532 Atomic!(T) atom;
1533
1534 atom.m_val = val;
1535 assert( atom.m_val == base && incr == base );
1536 base = cast(T)( base + 1 );
1537 incr = atom.increment!(ms)();
1538 assert( atom.m_val == base && incr == base );
1539 }
1540 }
1541
1542
1543 template testDecrement( msync ms, T )
1544 {
1545 void testDecrement( T val = T.init + 1 )
1546 {
1547 T base = val;
1548 T decr = val;
1549 Atomic!(T) atom;
1550
1551 atom.m_val = val;
1552 assert( atom.m_val == base && decr == base );
1553 base = cast(T)( base - 1 );
1554 decr = atom.decrement!(ms)();
1555 assert( atom.m_val == base && decr == base );
1556 }
1557 }
1558
1559
1560 template testType( T )
1561 {
1562 void testType( T val = T.init +1 )
1563 {
1564 testLoad!(msync.raw, T)( val );
1565 testLoad!(msync.hlb, T)( val );
1566 testLoad!(msync.acq, T)( val );
1567 testLoad!(msync.seq, T)( val );
1568
1569 testStore!(msync.raw, T)( val );
1570 testStore!(msync.ssb, T)( val );
1571 testStore!(msync.acq, T)( val );
1572 testStore!(msync.rel, T)( val );
1573 testStore!(msync.seq, T)( val );
1574
1575 testStoreIf!(msync.raw, T)( val );
1576 testStoreIf!(msync.ssb, T)( val );
1577 testStoreIf!(msync.acq, T)( val );
1578 testStoreIf!(msync.rel, T)( val );
1579 testStoreIf!(msync.seq, T)( val );
1580
1581 static if( isValidNumericType!(T) )
1582 {
1583 testIncrement!(msync.raw, T)( val );
1584 testIncrement!(msync.ssb, T)( val );
1585 testIncrement!(msync.acq, T)( val );
1586 testIncrement!(msync.rel, T)( val );
1587 testIncrement!(msync.seq, T)( val );
1588
1589 testDecrement!(msync.raw, T)( val );
1590 testDecrement!(msync.ssb, T)( val );
1591 testDecrement!(msync.acq, T)( val );
1592 testDecrement!(msync.rel, T)( val );
1593 testDecrement!(msync.seq, T)( val );
1594 }
1595 }
1596 }
1597 }
1598 }
1599
1600
1601 ////////////////////////////////////////////////////////////////////////////////
1602 // Unit Tests
1603 ////////////////////////////////////////////////////////////////////////////////
1604
1605
1606 debug( UnitTest )
1607 {
1608 unittest
1609 {
1610 testType!(bool)();
1611
1612 testType!(byte)();
1613 testType!(ubyte)();
1614
1615 testType!(short)();
1616 testType!(ushort)();
1617
1618 testType!(int)();
1619 testType!(uint)();
1620
1621 int x;
1622 testType!(void*)( &x );
1623
1624 version( Has64BitOps )
1625 {
1626 testType!(long)();
1627 testType!(ulong)();
1628 }
1629 else version( Has64BitCAS )
1630 {
1631 testStoreIf!(msync.raw, long)();
1632 testStoreIf!(msync.ssb, long)();
1633 testStoreIf!(msync.acq, long)();
1634 testStoreIf!(msync.rel, long)();
1635 testStoreIf!(msync.seq, long)();
1636
1637 testStoreIf!(msync.raw, ulong)();
1638 testStoreIf!(msync.ssb, ulong)();
1639 testStoreIf!(msync.acq, ulong)();
1640 testStoreIf!(msync.rel, ulong)();
1641 testStoreIf!(msync.seq, ulong)();
1642 }
1643 }
1644 }