arch/x86/include/asm/bitops.h

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