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