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 defined(__x86_64__) || defined(__i386__)
  31
  32 // Returns UINT_MAX if all the bits in p were already set.
  33 DISPATCH_ALWAYS_INLINE
  34 static inline unsigned int
  35 os_atomic_set_first_bit(volatile unsigned long *p, unsigned int max)
  36 {
  37         unsigned long val, bit;
  38         if (max > (sizeof(val) * 8)) {
  39                 __asm__ (
  40                                  "1: \n\t"
  41                                  "mov   %[_p], %[_val] \n\t"
  42                                  "not   %[_val] \n\t"
  43                                  "bsf   %[_val], %[_bit] \n\t" /* val is 0 => set zf */
  44                                  "jz    2f \n\t"
  45                                  "lock \n\t"
  46                                  "bts   %[_bit], %[_p] \n\t" /* cf = prev bit val */
  47                                  "jc    1b \n\t" /* lost race, retry */
  48                                  "jmp   3f \n\t"
  49                                  "2: \n\t"
  50                                  "mov   %[_all_ones], %[_bit]" "\n\t"
  51                                  "3: \n\t"
  52                                  : [_p] "=m" (*p), [_val] "=&r" (val), [_bit] "=&r" (bit)
  53                                  : [_all_ones] "i" ((typeof(bit))UINT_MAX) : "memory", "cc");
  54         } else {
  55                 __asm__ (
  56                                  "1: \n\t"
  57                                  "mov   %[_p], %[_val] \n\t"
  58                                  "not   %[_val] \n\t"
  59                                  "bsf   %[_val], %[_bit] \n\t" /* val is 0 => set zf */
  60                                  "jz    2f \n\t"
  61                                  "cmp   %[_max], %[_bit] \n\t"
  62                                  "jg    2f \n\t"
  63                                  "lock \n\t"
  64                                  "bts   %[_bit], %[_p] \n\t" /* cf = prev bit val */
  65                                  "jc    1b \n\t" /* lost race, retry */
  66                                  "jmp   3f \n\t"
  67                                  "2: \n\t"
  68                                  "mov   %[_all_ones], %[_bit]" "\n\t"
  69                                  "3: \n\t"
  70                                  : [_p] "=m" (*p), [_val] "=&r" (val), [_bit] "=&r" (bit)
  71                                  : [_all_ones] "i" ((typeof(bit))UINT_MAX),
  72                                    [_max] "g" ((typeof(bit))max) : "memory", "cc");
  73         }
  74         return (unsigned int)bit;
  75 }
  76
  77 #else
  78
  79 #if __clang__ && __clang_major__ < 5 // <rdar://problem/13833871>
  80 #define __builtin_ffs(x) __builtin_ffs((unsigned int)(x))
  81 #endif
  82
  83 DISPATCH_ALWAYS_INLINE
  84 static inline unsigned int
  85 os_atomic_set_first_bit(volatile unsigned long *p, unsigned int max_index)
  86 {
  87         unsigned int index;
  88         unsigned long b, b_masked;
  89
  90         os_atomic_rmw_loop(p, b, b_masked, relaxed, {
  91                 // ffs returns 1 + index, or 0 if none set
  92                 index = (unsigned int)__builtin_ffsl((long)~b);
  93                 if (slowpath(index == 0)) {
  94                         os_atomic_rmw_loop_give_up(return UINT_MAX);
  95                 }
  96                 index--;
  97                 if (slowpath(index > max_index)) {
  98                         os_atomic_rmw_loop_give_up(return UINT_MAX);
  99                 }
 100                 b_masked = b | (1UL << index);
 101         });
 102
 103         return index;
 104 }
 105
 106 #endif
 107
 108 #endif // __DISPATCH_SHIMS_ATOMIC_SFB__