1 /* SPDX-License-Identifier: GPL-2.0 */ 2 #ifndef _ASM_X86_BITOPS_H 3 #define _ASM_X86_BITOPS_H 4 5 /* 6 * Copyright 1992, Linus Torvalds. 7 * 8 * Note: inlines with more than a single statement should be marked 9 * __always_inline to avoid problems with older gcc's inlining heuristics. 10 */ 11 12 #ifndef _LINUX_BITOPS_H 13 #error only <linux/bitops.h> can be included directly 14 #endif 15 16 #include <linux/compiler.h> 17 #include <asm/alternative.h> 18 #include <asm/rmwcc.h> 19 #include <asm/barrier.h> 20 21 #if BITS_PER_LONG == 32 22 # define _BITOPS_LONG_SHIFT 5 23 #elif BITS_PER_LONG == 64 24 # define _BITOPS_LONG_SHIFT 6 25 #else 26 # error "Unexpected BITS_PER_LONG" 27 #endif 28 29 #define BIT_64(n) (U64_C(1) << (n)) 30 31 /* 32 * These have to be done with inline assembly: that way the bit-setting 33 * is guaranteed to be atomic. All bit operations return 0 if the bit 34 * was cleared before the operation and != 0 if it was not. 35 * 36 * bit 0 is the LSB of addr; bit 32 is the LSB of (addr+1). 37 */ 38 39 #define RLONG_ADDR(x) "m" (*(volatile long *) (x)) 40 #define WBYTE_ADDR(x) "+m" (*(volatile char *) (x)) 41 42 #define ADDR RLONG_ADDR(addr) 43 44 /* 45 * We do the locked ops that don't return the old value as 46 * a mask operation on a byte. 47 */ 48 #define IS_IMMEDIATE(nr) (__builtin_constant_p(nr)) 49 #define CONST_MASK_ADDR(nr, addr) WBYTE_ADDR((void *)(addr) + ((nr)>>3)) 50 #define CONST_MASK(nr) (1 << ((nr) & 7)) 51 52 static __always_inline void 53 arch_set_bit(long nr, volatile unsigned long *addr) 54 { 55 if (IS_IMMEDIATE(nr)) { 56 asm volatile(LOCK_PREFIX "orb %1,%0" 57 : CONST_MASK_ADDR(nr, addr) 58 : "iq" ((u8)CONST_MASK(nr)) 59 : "memory"); 60 } else { 61 asm volatile(LOCK_PREFIX __ASM_SIZE(bts) " %1,%0" 62 : : RLONG_ADDR(addr), "Ir" (nr) : "memory"); 63 } 64 } 65 66 static __always_inline void 67 arch___set_bit(long nr, volatile unsigned long *addr) 68 { 69 asm volatile(__ASM_SIZE(bts) " %1,%0" : : ADDR, "Ir" (nr) : "memory"); 70 } 71 72 static __always_inline void 73 arch_clear_bit(long nr, volatile unsigned long *addr) 74 { 75 if (IS_IMMEDIATE(nr)) { 76 asm volatile(LOCK_PREFIX "andb %1,%0" 77 : CONST_MASK_ADDR(nr, addr) 78 : "iq" ((u8)~CONST_MASK(nr))); 79 } else { 80 asm volatile(LOCK_PREFIX __ASM_SIZE(btr) " %1,%0" 81 : : RLONG_ADDR(addr), "Ir" (nr) : "memory"); 82 } 83 } 84 85 static __always_inline void 86 arch_clear_bit_unlock(long nr, volatile unsigned long *addr) 87 { 88 barrier(); 89 arch_clear_bit(nr, addr); 90 } 91 92 static __always_inline void 93 arch___clear_bit(long nr, volatile unsigned long *addr) 94 { 95 asm volatile(__ASM_SIZE(btr) " %1,%0" : : ADDR, "Ir" (nr) : "memory"); 96 } 97 98 static __always_inline bool 99 arch_clear_bit_unlock_is_negative_byte(long nr, volatile unsigned long *addr) 100 { 101 bool negative; 102 asm volatile(LOCK_PREFIX "andb %2,%1" 103 CC_SET(s) 104 : CC_OUT(s) (negative), WBYTE_ADDR(addr) 105 : "ir" ((char) ~(1 << nr)) : "memory"); 106 return negative; 107 } 108 #define arch_clear_bit_unlock_is_negative_byte \ 109 arch_clear_bit_unlock_is_negative_byte 110 111 static __always_inline void 112 arch___clear_bit_unlock(long nr, volatile unsigned long *addr) 113 { 114 arch___clear_bit(nr, addr); 115 } 116 117 static __always_inline void 118 arch___change_bit(long nr, volatile unsigned long *addr) 119 { 120 asm volatile(__ASM_SIZE(btc) " %1,%0" : : ADDR, "Ir" (nr) : "memory"); 121 } 122 123 static __always_inline void 124 arch_change_bit(long nr, volatile unsigned long *addr) 125 { 126 if (IS_IMMEDIATE(nr)) { 127 asm volatile(LOCK_PREFIX "xorb %1,%0" 128 : CONST_MASK_ADDR(nr, addr) 129 : "iq" ((u8)CONST_MASK(nr))); 130 } else { 131 asm volatile(LOCK_PREFIX __ASM_SIZE(btc) " %1,%0" 132 : : RLONG_ADDR(addr), "Ir" (nr) : "memory"); 133 } 134 } 135 136 static __always_inline bool 137 arch_test_and_set_bit(long nr, volatile unsigned long *addr) 138 { 139 return GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(bts), *addr, c, "Ir", nr); 140 } 141 142 static __always_inline bool 143 arch_test_and_set_bit_lock(long nr, volatile unsigned long *addr) 144 { 145 return arch_test_and_set_bit(nr, addr); 146 } 147 148 static __always_inline bool 149 arch___test_and_set_bit(long nr, volatile unsigned long *addr) 150 { 151 bool oldbit; 152 153 asm(__ASM_SIZE(bts) " %2,%1" 154 CC_SET(c) 155 : CC_OUT(c) (oldbit) 156 : ADDR, "Ir" (nr) : "memory"); 157 return oldbit; 158 } 159 160 static __always_inline bool 161 arch_test_and_clear_bit(long nr, volatile unsigned long *addr) 162 { 163 return GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(btr), *addr, c, "Ir", nr); 164 } 165 166 /* 167 * Note: the operation is performed atomically with respect to 168 * the local CPU, but not other CPUs. Portable code should not 169 * rely on this behaviour. 170 * KVM relies on this behaviour on x86 for modifying memory that is also 171 * accessed from a hypervisor on the same CPU if running in a VM: don't change 172 * this without also updating arch/x86/kernel/kvm.c 173 */ 174 static __always_inline bool 175 arch___test_and_clear_bit(long nr, volatile unsigned long *addr) 176 { 177 bool oldbit; 178 179 asm volatile(__ASM_SIZE(btr) " %2,%1" 180 CC_SET(c) 181 : CC_OUT(c) (oldbit) 182 : ADDR, "Ir" (nr) : "memory"); 183 return oldbit; 184 } 185 186 static __always_inline bool 187 arch___test_and_change_bit(long nr, volatile unsigned long *addr) 188 { 189 bool oldbit; 190 191 asm volatile(__ASM_SIZE(btc) " %2,%1" 192 CC_SET(c) 193 : CC_OUT(c) (oldbit) 194 : ADDR, "Ir" (nr) : "memory"); 195 196 return oldbit; 197 } 198 199 static __always_inline bool 200 arch_test_and_change_bit(long nr, volatile unsigned long *addr) 201 { 202 return GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(btc), *addr, c, "Ir", nr); 203 } 204 205 static __always_inline bool constant_test_bit(long nr, const volatile unsigned long *addr) 206 { 207 return ((1UL << (nr & (BITS_PER_LONG-1))) & 208 (addr[nr >> _BITOPS_LONG_SHIFT])) != 0; 209 } 210 211 static __always_inline bool variable_test_bit(long nr, volatile const unsigned long *addr) 212 { 213 bool oldbit; 214 215 asm volatile(__ASM_SIZE(bt) " %2,%1" 216 CC_SET(c) 217 : CC_OUT(c) (oldbit) 218 : "m" (*(unsigned long *)addr), "Ir" (nr) : "memory"); 219 220 return oldbit; 221 } 222 223 #define arch_test_bit(nr, addr) \ 224 (__builtin_constant_p((nr)) \ 225 ? constant_test_bit((nr), (addr)) \ 226 : variable_test_bit((nr), (addr))) 227 228 /** 229 * __ffs - find first set bit in word 230 * @word: The word to search 231 * 232 * Undefined if no bit exists, so code should check against 0 first. 233 */ 234 static __always_inline unsigned long __ffs(unsigned long word) 235 { 236 asm("rep; bsf %1,%0" 237 : "=r" (word) 238 : "rm" (word)); 239 return word; 240 } 241 242 /** 243 * ffz - find first zero bit in word 244 * @word: The word to search 245 * 246 * Undefined if no zero exists, so code should check against ~0UL first. 247 */ 248 static __always_inline unsigned long ffz(unsigned long word) 249 { 250 asm("rep; bsf %1,%0" 251 : "=r" (word) 252 : "r" (~word)); 253 return word; 254 } 255 256 /* 257 * __fls: find last set bit in word 258 * @word: The word to search 259 * 260 * Undefined if no set bit exists, so code should check against 0 first. 261 */ 262 static __always_inline unsigned long __fls(unsigned long word) 263 { 264 asm("bsr %1,%0" 265 : "=r" (word) 266 : "rm" (word)); 267 return word; 268 } 269 270 #undef ADDR 271 272 #ifdef __KERNEL__ 273 /** 274 * ffs - find first set bit in word 275 * @x: the word to search 276 * 277 * This is defined the same way as the libc and compiler builtin ffs 278 * routines, therefore differs in spirit from the other bitops. 279 * 280 * ffs(value) returns 0 if value is 0 or the position of the first 281 * set bit if value is nonzero. The first (least significant) bit 282 * is at position 1. 283 */ 284 static __always_inline int ffs(int x) 285 { 286 int r; 287 288 #ifdef CONFIG_X86_64 289 /* 290 * AMD64 says BSFL won't clobber the dest reg if x==0; Intel64 says the 291 * dest reg is undefined if x==0, but their CPU architect says its 292 * value is written to set it to the same as before, except that the 293 * top 32 bits will be cleared. 294 * 295 * We cannot do this on 32 bits because at the very least some 296 * 486 CPUs did not behave this way. 297 */ 298 asm("bsfl %1,%0" 299 : "=r" (r) 300 : "rm" (x), "0" (-1)); 301 #elif defined(CONFIG_X86_CMOV) 302 asm("bsfl %1,%0\n\t" 303 "cmovzl %2,%0" 304 : "=&r" (r) : "rm" (x), "r" (-1)); 305 #else 306 asm("bsfl %1,%0\n\t" 307 "jnz 1f\n\t" 308 "movl $-1,%0\n" 309 "1:" : "=r" (r) : "rm" (x)); 310 #endif 311 return r + 1; 312 } 313 314 /** 315 * fls - find last set bit in word 316 * @x: the word to search 317 * 318 * This is defined in a similar way as the libc and compiler builtin 319 * ffs, but returns the position of the most significant set bit. 320 * 321 * fls(value) returns 0 if value is 0 or the position of the last 322 * set bit if value is nonzero. The last (most significant) bit is 323 * at position 32. 324 */ 325 static __always_inline int fls(unsigned int x) 326 { 327 int r; 328 329 #ifdef CONFIG_X86_64 330 /* 331 * AMD64 says BSRL won't clobber the dest reg if x==0; Intel64 says the 332 * dest reg is undefined if x==0, but their CPU architect says its 333 * value is written to set it to the same as before, except that the 334 * top 32 bits will be cleared. 335 * 336 * We cannot do this on 32 bits because at the very least some 337 * 486 CPUs did not behave this way. 338 */ 339 asm("bsrl %1,%0" 340 : "=r" (r) 341 : "rm" (x), "0" (-1)); 342 #elif defined(CONFIG_X86_CMOV) 343 asm("bsrl %1,%0\n\t" 344 "cmovzl %2,%0" 345 : "=&r" (r) : "rm" (x), "rm" (-1)); 346 #else 347 asm("bsrl %1,%0\n\t" 348 "jnz 1f\n\t" 349 "movl $-1,%0\n" 350 "1:" : "=r" (r) : "rm" (x)); 351 #endif 352 return r + 1; 353 } 354 355 /** 356 * fls64 - find last set bit in a 64-bit word 357 * @x: the word to search 358 * 359 * This is defined in a similar way as the libc and compiler builtin 360 * ffsll, but returns the position of the most significant set bit. 361 * 362 * fls64(value) returns 0 if value is 0 or the position of the last 363 * set bit if value is nonzero. The last (most significant) bit is 364 * at position 64. 365 */ 366 #ifdef CONFIG_X86_64 367 static __always_inline int fls64(__u64 x) 368 { 369 int bitpos = -1; 370 /* 371 * AMD64 says BSRQ won't clobber the dest reg if x==0; Intel64 says the 372 * dest reg is undefined if x==0, but their CPU architect says its 373 * value is written to set it to the same as before. 374 */ 375 asm("bsrq %1,%q0" 376 : "+r" (bitpos) 377 : "rm" (x)); 378 return bitpos + 1; 379 } 380 #else 381 #include <asm-generic/bitops/fls64.h> 382 #endif 383 384 #include <asm-generic/bitops/find.h> 385 386 #include <asm-generic/bitops/sched.h> 387 388 #include <asm/arch_hweight.h> 389 390 #include <asm-generic/bitops/const_hweight.h> 391 392 #include <asm-generic/bitops-instrumented.h> 393 394 #include <asm-generic/bitops/le.h> 395 396 #include <asm-generic/bitops/ext2-atomic-setbit.h> 397 398 #endif /* __KERNEL__ */ 399 #endif /* _ASM_X86_BITOPS_H */ 400