src/shims/atomic_sfb.h

   1 /*
   2  * Copyright (c) 2012-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_APACHE_LICENSE_HEADER_START@
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *
  18  * @APPLE_APACHE_LICENSE_HEADER_END@
  19  */
  20
  21 /*
  22  * IMPORTANT: This header file describes INTERNAL interfaces to libdispatch
  23  * which are subject to change in future releases of Mac OS X. Any applications
  24  * relying on these interfaces WILL break.
  25  */
  26
  27 #ifndef __DISPATCH_SHIMS_ATOMIC_SFB__
  28 #define __DISPATCH_SHIMS_ATOMIC_SFB__
  29
  30 #if __clang__ && __clang_major__ < 5 // <rdar://problem/13833871>
  31 #define __builtin_ffs(x) __builtin_ffs((unsigned int)(x))
  32 #endif
  33
  34 // Returns UINT_MAX if all the bits in p were already set.
  35 #define dispatch_atomic_set_first_bit(p,m) _dispatch_atomic_set_first_bit(p,m)
  36
  37 DISPATCH_ALWAYS_INLINE
  38 static inline unsigned int
  39 _dispatch_atomic_set_first_bit(volatile unsigned long *p,
  40                 unsigned int max_index)
  41 {
  42         unsigned int index;
  43         unsigned long b, mask, b_masked;
  44
  45         for (;;) {
  46                 b = *p;
  47                 // ffs returns 1 + index, or 0 if none set.
  48                 index = (unsigned int)__builtin_ffsl((long)~b);
  49                 if (slowpath(index == 0)) {
  50                         return UINT_MAX;
  51                 }
  52                 index--;
  53                 if (slowpath(index > max_index)) {
  54                         return UINT_MAX;
  55                 }
  56                 mask = ((typeof(b))1) << index;
  57                 b_masked = b | mask;
  58                 if (__sync_bool_compare_and_swap(p, b, b_masked)) {
  59                         return index;
  60                 }
  61         }
  62 }
  63
  64 #if defined(__x86_64__) || defined(__i386__)
  65
  66 #undef dispatch_atomic_set_first_bit
  67 DISPATCH_ALWAYS_INLINE
  68 static inline unsigned int
  69 dispatch_atomic_set_first_bit(volatile unsigned long *p, unsigned int max)
  70 {
  71         unsigned long val, bit;
  72         if (max > (sizeof(val) * 8)) {
  73                 __asm__ (
  74                                  "1: \n\t"
  75                                  "mov   %[_p], %[_val] \n\t"
  76                                  "not   %[_val] \n\t"
  77                                  "bsf   %[_val], %[_bit] \n\t" /* val is 0 => set zf */
  78                                  "jz    2f \n\t"
  79                                  "lock \n\t"
  80                                  "bts   %[_bit], %[_p] \n\t" /* cf = prev bit val */
  81                                  "jc    1b \n\t" /* lost race, retry */
  82                                  "jmp   3f \n\t"
  83                                  "2: \n\t"
  84                                  "mov   %[_all_ones], %[_bit]" "\n\t"
  85                                  "3: \n\t"
  86                                  : [_p] "=m" (*p), [_val] "=&r" (val), [_bit] "=&r" (bit)
  87                                  : [_all_ones] "i" ((typeof(bit))UINT_MAX) : "memory", "cc");
  88         } else {
  89                 __asm__ (
  90                                  "1: \n\t"
  91                                  "mov   %[_p], %[_val] \n\t"
  92                                  "not   %[_val] \n\t"
  93                                  "bsf   %[_val], %[_bit] \n\t" /* val is 0 => set zf */
  94                                  "jz    2f \n\t"
  95                                  "cmp   %[_max], %[_bit] \n\t"
  96                                  "jg    2f \n\t"
  97                                  "lock \n\t"
  98                                  "bts   %[_bit], %[_p] \n\t" /* cf = prev bit val */
  99                                  "jc    1b \n\t" /* lost race, retry */
 100                                  "jmp   3f \n\t"
 101                                  "2: \n\t"
 102                                  "mov   %[_all_ones], %[_bit]" "\n\t"
 103                                  "3: \n\t"
 104                                  : [_p] "=m" (*p), [_val] "=&r" (val), [_bit] "=&r" (bit)
 105                                  : [_all_ones] "i" ((typeof(bit))UINT_MAX),
 106                                    [_max] "g" ((typeof(bit))max) : "memory", "cc");
 107         }
 108         return (unsigned int)bit;
 109 }
 110
 111 #endif
 112
 113
 114 #endif // __DISPATCH_SHIMS_ATOMIC_SFB__