1 /* SPDX-License-Identifier: GPL-2.0 */ 2 #ifndef _LINUX_BITOPS_H 3 #define _LINUX_BITOPS_H 4 5 #include <asm/types.h> 6 #include <linux/bits.h> 7 #include <linux/typecheck.h> 8 9 #include <uapi/linux/kernel.h> 10 11 #define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE) 12 #define BITS_TO_LONGS(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(long)) 13 #define BITS_TO_U64(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u64)) 14 #define BITS_TO_U32(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u32)) 15 #define BITS_TO_BYTES(nr) __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(char)) 16 17 #define BYTES_TO_BITS(nb) ((nb) * BITS_PER_BYTE) 18 19 extern unsigned int __sw_hweight8(unsigned int w); 20 extern unsigned int __sw_hweight16(unsigned int w); 21 extern unsigned int __sw_hweight32(unsigned int w); 22 extern unsigned long __sw_hweight64(__u64 w); 23 24 /* 25 * Defined here because those may be needed by architecture-specific static 26 * inlines. 27 */ 28 29 #include <asm-generic/bitops/generic-non-atomic.h> 30 31 /* 32 * Many architecture-specific non-atomic bitops contain inline asm code and due 33 * to that the compiler can't optimize them to compile-time expressions or 34 * constants. In contrary, generic_*() helpers are defined in pure C and 35 * compilers optimize them just well. 36 * Therefore, to make `unsigned long foo = 0; __set_bit(BAR, &foo)` effectively 37 * equal to `unsigned long foo = BIT(BAR)`, pick the generic C alternative when 38 * the arguments can be resolved at compile time. That expression itself is a 39 * constant and doesn't bring any functional changes to the rest of cases. 40 * The casts to `uintptr_t` are needed to mitigate `-Waddress` warnings when 41 * passing a bitmap from .bss or .data (-> `!!addr` is always true). 42 */ 43 #define bitop(op, nr, addr) \ 44 ((__builtin_constant_p(nr) && \ 45 __builtin_constant_p((uintptr_t)(addr) != (uintptr_t)NULL) && \ 46 (uintptr_t)(addr) != (uintptr_t)NULL && \ 47 __builtin_constant_p(*(const unsigned long *)(addr))) ? \ 48 const##op(nr, addr) : op(nr, addr)) 49 50 #define __set_bit(nr, addr) bitop(___set_bit, nr, addr) 51 #define __clear_bit(nr, addr) bitop(___clear_bit, nr, addr) 52 #define __change_bit(nr, addr) bitop(___change_bit, nr, addr) 53 #define __test_and_set_bit(nr, addr) bitop(___test_and_set_bit, nr, addr) 54 #define __test_and_clear_bit(nr, addr) bitop(___test_and_clear_bit, nr, addr) 55 #define __test_and_change_bit(nr, addr) bitop(___test_and_change_bit, nr, addr) 56 #define test_bit(nr, addr) bitop(_test_bit, nr, addr) 57 #define test_bit_acquire(nr, addr) bitop(_test_bit_acquire, nr, addr) 58 59 /* 60 * Include this here because some architectures need generic_ffs/fls in 61 * scope 62 */ 63 #include <asm/bitops.h> 64 65 /* Check that the bitops prototypes are sane */ 66 #define __check_bitop_pr(name) \ 67 static_assert(__same_type(arch_##name, generic_##name) && \ 68 __same_type(const_##name, generic_##name) && \ 69 __same_type(_##name, generic_##name)) 70 71 __check_bitop_pr(__set_bit); 72 __check_bitop_pr(__clear_bit); 73 __check_bitop_pr(__change_bit); 74 __check_bitop_pr(__test_and_set_bit); 75 __check_bitop_pr(__test_and_clear_bit); 76 __check_bitop_pr(__test_and_change_bit); 77 __check_bitop_pr(test_bit); 78 __check_bitop_pr(test_bit_acquire); 79 80 #undef __check_bitop_pr 81 82 static inline int get_bitmask_order(unsigned int count) 83 { 84 int order; 85 86 order = fls(count); 87 return order; /* We could be slightly more clever with -1 here... */ 88 } 89 90 static __always_inline unsigned long hweight_long(unsigned long w) 91 { 92 return sizeof(w) == 4 ? hweight32(w) : hweight64((__u64)w); 93 } 94 95 /** 96 * rol64 - rotate a 64-bit value left 97 * @word: value to rotate 98 * @shift: bits to roll 99 */ 100 static inline __u64 rol64(__u64 word, unsigned int shift) 101 { 102 return (word << (shift & 63)) | (word >> ((-shift) & 63)); 103 } 104 105 /** 106 * ror64 - rotate a 64-bit value right 107 * @word: value to rotate 108 * @shift: bits to roll 109 */ 110 static inline __u64 ror64(__u64 word, unsigned int shift) 111 { 112 return (word >> (shift & 63)) | (word << ((-shift) & 63)); 113 } 114 115 /** 116 * rol32 - rotate a 32-bit value left 117 * @word: value to rotate 118 * @shift: bits to roll 119 */ 120 static inline __u32 rol32(__u32 word, unsigned int shift) 121 { 122 return (word << (shift & 31)) | (word >> ((-shift) & 31)); 123 } 124 125 /** 126 * ror32 - rotate a 32-bit value right 127 * @word: value to rotate 128 * @shift: bits to roll 129 */ 130 static inline __u32 ror32(__u32 word, unsigned int shift) 131 { 132 return (word >> (shift & 31)) | (word << ((-shift) & 31)); 133 } 134 135 /** 136 * rol16 - rotate a 16-bit value left 137 * @word: value to rotate 138 * @shift: bits to roll 139 */ 140 static inline __u16 rol16(__u16 word, unsigned int shift) 141 { 142 return (word << (shift & 15)) | (word >> ((-shift) & 15)); 143 } 144 145 /** 146 * ror16 - rotate a 16-bit value right 147 * @word: value to rotate 148 * @shift: bits to roll 149 */ 150 static inline __u16 ror16(__u16 word, unsigned int shift) 151 { 152 return (word >> (shift & 15)) | (word << ((-shift) & 15)); 153 } 154 155 /** 156 * rol8 - rotate an 8-bit value left 157 * @word: value to rotate 158 * @shift: bits to roll 159 */ 160 static inline __u8 rol8(__u8 word, unsigned int shift) 161 { 162 return (word << (shift & 7)) | (word >> ((-shift) & 7)); 163 } 164 165 /** 166 * ror8 - rotate an 8-bit value right 167 * @word: value to rotate 168 * @shift: bits to roll 169 */ 170 static inline __u8 ror8(__u8 word, unsigned int shift) 171 { 172 return (word >> (shift & 7)) | (word << ((-shift) & 7)); 173 } 174 175 /** 176 * sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit 177 * @value: value to sign extend 178 * @index: 0 based bit index (0<=index<32) to sign bit 179 * 180 * This is safe to use for 16- and 8-bit types as well. 181 */ 182 static __always_inline __s32 sign_extend32(__u32 value, int index) 183 { 184 __u8 shift = 31 - index; 185 return (__s32)(value << shift) >> shift; 186 } 187 188 /** 189 * sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit 190 * @value: value to sign extend 191 * @index: 0 based bit index (0<=index<64) to sign bit 192 */ 193 static __always_inline __s64 sign_extend64(__u64 value, int index) 194 { 195 __u8 shift = 63 - index; 196 return (__s64)(value << shift) >> shift; 197 } 198 199 static inline unsigned int fls_long(unsigned long l) 200 { 201 if (sizeof(l) == 4) 202 return fls(l); 203 return fls64(l); 204 } 205 206 static inline int get_count_order(unsigned int count) 207 { 208 if (count == 0) 209 return -1; 210 211 return fls(--count); 212 } 213 214 /** 215 * get_count_order_long - get order after rounding @l up to power of 2 216 * @l: parameter 217 * 218 * it is same as get_count_order() but with long type parameter 219 */ 220 static inline int get_count_order_long(unsigned long l) 221 { 222 if (l == 0UL) 223 return -1; 224 return (int)fls_long(--l); 225 } 226 227 /** 228 * __ffs64 - find first set bit in a 64 bit word 229 * @word: The 64 bit word 230 * 231 * On 64 bit arches this is a synonym for __ffs 232 * The result is not defined if no bits are set, so check that @word 233 * is non-zero before calling this. 234 */ 235 static inline unsigned int __ffs64(u64 word) 236 { 237 #if BITS_PER_LONG == 32 238 if (((u32)word) == 0UL) 239 return __ffs((u32)(word >> 32)) + 32; 240 #elif BITS_PER_LONG != 64 241 #error BITS_PER_LONG not 32 or 64 242 #endif 243 return __ffs((unsigned long)word); 244 } 245 246 /** 247 * fns - find N'th set bit in a word 248 * @word: The word to search 249 * @n: Bit to find 250 */ 251 static inline unsigned int fns(unsigned long word, unsigned int n) 252 { 253 while (word && n--) 254 word &= word - 1; 255 256 return word ? __ffs(word) : BITS_PER_LONG; 257 } 258 259 /** 260 * assign_bit - Assign value to a bit in memory 261 * @nr: the bit to set 262 * @addr: the address to start counting from 263 * @value: the value to assign 264 */ 265 #define assign_bit(nr, addr, value) \ 266 ((value) ? set_bit((nr), (addr)) : clear_bit((nr), (addr))) 267 268 #define __assign_bit(nr, addr, value) \ 269 ((value) ? __set_bit((nr), (addr)) : __clear_bit((nr), (addr))) 270 271 /** 272 * __ptr_set_bit - Set bit in a pointer's value 273 * @nr: the bit to set 274 * @addr: the address of the pointer variable 275 * 276 * Example: 277 * void *p = foo(); 278 * __ptr_set_bit(bit, &p); 279 */ 280 #define __ptr_set_bit(nr, addr) \ 281 ({ \ 282 typecheck_pointer(*(addr)); \ 283 __set_bit(nr, (unsigned long *)(addr)); \ 284 }) 285 286 /** 287 * __ptr_clear_bit - Clear bit in a pointer's value 288 * @nr: the bit to clear 289 * @addr: the address of the pointer variable 290 * 291 * Example: 292 * void *p = foo(); 293 * __ptr_clear_bit(bit, &p); 294 */ 295 #define __ptr_clear_bit(nr, addr) \ 296 ({ \ 297 typecheck_pointer(*(addr)); \ 298 __clear_bit(nr, (unsigned long *)(addr)); \ 299 }) 300 301 /** 302 * __ptr_test_bit - Test bit in a pointer's value 303 * @nr: the bit to test 304 * @addr: the address of the pointer variable 305 * 306 * Example: 307 * void *p = foo(); 308 * if (__ptr_test_bit(bit, &p)) { 309 * ... 310 * } else { 311 * ... 312 * } 313 */ 314 #define __ptr_test_bit(nr, addr) \ 315 ({ \ 316 typecheck_pointer(*(addr)); \ 317 test_bit(nr, (unsigned long *)(addr)); \ 318 }) 319 320 #ifdef __KERNEL__ 321 322 #ifndef set_mask_bits 323 #define set_mask_bits(ptr, mask, bits) \ 324 ({ \ 325 const typeof(*(ptr)) mask__ = (mask), bits__ = (bits); \ 326 typeof(*(ptr)) old__, new__; \ 327 \ 328 old__ = READ_ONCE(*(ptr)); \ 329 do { \ 330 new__ = (old__ & ~mask__) | bits__; \ 331 } while (!try_cmpxchg(ptr, &old__, new__)); \ 332 \ 333 old__; \ 334 }) 335 #endif 336 337 #ifndef bit_clear_unless 338 #define bit_clear_unless(ptr, clear, test) \ 339 ({ \ 340 const typeof(*(ptr)) clear__ = (clear), test__ = (test);\ 341 typeof(*(ptr)) old__, new__; \ 342 \ 343 old__ = READ_ONCE(*(ptr)); \ 344 do { \ 345 if (old__ & test__) \ 346 break; \ 347 new__ = old__ & ~clear__; \ 348 } while (!try_cmpxchg(ptr, &old__, new__)); \ 349 \ 350 !(old__ & test__); \ 351 }) 352 #endif 353 354 #endif /* __KERNEL__ */ 355 #endif 356