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
_dispatch_atomic_set_first_bit(volatile unsigned long * p,unsigned int max_index)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
dispatch_atomic_set_first_bit(volatile unsigned long * p,unsigned int max)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__
115