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 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 */