Mirror of :pserver:cvs@cvs.fefe.de:/cvs libowfat https://www.fefe.de/libowfat/
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 

158 lines
4.3 KiB

  1. #ifndef CAS_H
  2. #define CAS_H
  3. #include <stddef.h>
  4. /* Atomic operations for lock-free data structures.
  5. * We operate on machine words and use size_t as a type.
  6. * CAS stands for Compare And Swap, the most common operation. */
  7. /* The API was inspired by the Linux kernel */
  8. #if defined(__INTEL_COMPILER) || (__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 1))
  9. #define USE_BUILTINS
  10. #endif
  11. /* if (*x == oldval) { *x=newval; return 1; } else return 0; */
  12. static inline int compare_and_swap(volatile size_t* x,size_t oldval,size_t newval) {
  13. #ifdef USE_BUILTINS
  14. return __sync_bool_compare_and_swap(x,oldval,newval);
  15. #elif defined(__i386__)
  16. char result;
  17. asm volatile ("lock; cmpxchgl %3, %0; setz %1" : "=m"(*x), "=q" (result) : "m" (*x), "r" (newval), "a" (oldval) : "memory");
  18. return result;
  19. #elif defined(__x86_64__)
  20. char result;
  21. asm volatile ("lock; cmpxchgq %3, %0; setz %1" : "=m"(*x), "=q" (result) : "m" (*x), "r" (newval), "a" (oldval) : "memory");
  22. return result;
  23. #else
  24. #error architecture not supported and gcc too old, edit CAS.h
  25. #endif
  26. }
  27. /* return *x += val; */
  28. static inline size_t atomic_add_return(size_t* x,size_t val) {
  29. #ifdef USE_BUILTINS
  30. return __sync_add_and_fetch(x,val);
  31. #elif defined(__i386__)
  32. size_t i = val;
  33. asm volatile ("lock; xaddl %1, %0" : "+m" (*x), "+r" (val) :: "memory" );
  34. return i + val;
  35. #elif defined(__x86_64__)
  36. size_t i = val;
  37. asm volatile ("lock; xaddq %1, %0" : "+m" (*x), "+r" (val) :: "memory" );
  38. return i + val;
  39. #else
  40. size_t y;
  41. for (y=*x; compare_and_swap(&x,y,y+val)==0; y=*x) ;
  42. return y+val;
  43. #endif
  44. }
  45. /* *x += val; */
  46. static inline void atomic_add(size_t* x,size_t val) {
  47. #ifdef USE_BUILTINS
  48. __sync_add_and_fetch(x,val);
  49. #elif defined(__i386__)
  50. asm volatile ("lock; addl %1, %0" : "+m" (*x) : "ir" (val) );
  51. #elif defined(__x86_64__)
  52. asm volatile ("lock; addq %1, %0" : "+m" (*x) : "ir" (val) );
  53. #else
  54. atomic_add_return(&x,val);
  55. #endif
  56. }
  57. static inline void atomic_inc(size_t* x) {
  58. #ifdef __i386__
  59. asm volatile ("lock; incl %0" : "+m" (*x) );
  60. #elif defined(__x86_64__)
  61. asm volatile ("lock; incq %0" : "+m" (*x) );
  62. #else
  63. atomic_add(x,1);
  64. #endif
  65. }
  66. static inline size_t atomic_inc_return(size_t* x) {
  67. return atomic_add_return(x,1);
  68. }
  69. static inline void atomic_dec(size_t* x) {
  70. #ifdef __i386__
  71. asm volatile ("lock; decl %0" : "+m" (*x) );
  72. #elif defined(__x86_64__)
  73. asm volatile ("lock; decq %0" : "+m" (*x) );
  74. #else
  75. atomic_add(x,-1);
  76. #endif
  77. }
  78. static inline size_t atomic_dec_return(size_t* x) {
  79. return atomic_add_return(x,-1);
  80. }
  81. /* *x |= val; */
  82. static inline void atomic_or(volatile size_t* x,size_t val) {
  83. #ifdef USE_BUILTINS
  84. __sync_or_and_fetch(x,val);
  85. #elif defined(__i386__)
  86. asm volatile ("lock; orl %1, %0" : "+m" (*x) : "r" (val) );
  87. #elif defined(__x86_64__)
  88. asm volatile ("lock; orq %1, %0" : "+m" (*x) : "r" (val) );
  89. #else
  90. #error architecture not supported and gcc too old, edit CAS.h
  91. #endif
  92. }
  93. /* *x &= val; */
  94. static inline void atomic_and(volatile size_t* x,size_t val) {
  95. #ifdef USE_BUILTINS
  96. __sync_and_and_fetch(x,val);
  97. #elif defined(__i386__)
  98. asm volatile ("lock; andl %1, %0" : "+m" (*x) : "r" (val) );
  99. #elif defined(__x86_64__)
  100. asm volatile ("lock; andq %1, %0" : "+m" (*x) : "r" (val) );
  101. #else
  102. #error architecture not supported and gcc too old, edit CAS.h
  103. #endif
  104. }
  105. /* Optimization barrier */
  106. /* The "volatile" is due to gcc bugs */
  107. #define barrier() __asm__ __volatile__("": : :"memory")
  108. #if defined(__i386__) || defined(__x86_64__)
  109. #define mb() asm volatile("mfence":::"memory")
  110. #define rmb() asm volatile("lfence":::"memory")
  111. #define wmb() asm volatile("sfence":::"memory")
  112. /* Atomic operations are already serializing on x86 */
  113. #define smp_mb__before_atomic_dec() barrier()
  114. #define smp_mb__after_atomic_dec() barrier()
  115. #define smp_mb__before_atomic_inc() barrier()
  116. #define smp_mb__after_atomic_inc() barrier()
  117. #elif defined(__powerpc__)
  118. #define mb() asm volatile("sync":::"memory")
  119. #define rmb() asm volatile("sync":::"memory")
  120. #define wmb() asm volatile("sync":::"memory")
  121. #define smp_mb__before_atomic_dec() mb()
  122. #define smp_mb__after_atomic_dec() mb()
  123. #define smp_mb__before_atomic_inc() mb()
  124. #define smp_mb__after_atomic_inc() mb()
  125. #elif defined(USE_BUILTINS)
  126. #define mb() __sync_synchronize()
  127. #define rmb() __sync_synchronize()
  128. #define wmb() __sync_synchronize()
  129. #endif
  130. #undef USE_BUILTINS
  131. #endif