1 /*- 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * Copyright (c) 2013-2017 Mellanox Technologies, Ltd. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice unmodified, this list of conditions, and the following 13 * disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 #ifndef _LINUXKPI_LINUX_BITOPS_H_ 30 #define _LINUXKPI_LINUX_BITOPS_H_ 31 32 #include <sys/param.h> 33 #include <sys/types.h> 34 #include <sys/systm.h> 35 #include <sys/errno.h> 36 #include <sys/libkern.h> 37 38 #define BIT(nr) (1UL << (nr)) 39 #define BIT_ULL(nr) (1ULL << (nr)) 40 #define BITS_PER_LONG (__SIZEOF_LONG__ * __CHAR_BIT__) 41 #define BITS_PER_LONG_LONG (__SIZEOF_LONG_LONG__ * __CHAR_BIT__) 42 43 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 44 #define BITMAP_LAST_WORD_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 45 #define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 46 #define BIT_MASK(nr) (1UL << ((nr) & (BITS_PER_LONG - 1))) 47 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 48 #define GENMASK(h, l) (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l))) 49 #define GENMASK_ULL(h, l) (((~0ULL) >> (BITS_PER_LONG_LONG - (h) - 1)) & ((~0ULL) << (l))) 50 #define BITS_PER_BYTE 8 51 #define BITS_PER_TYPE(t) (sizeof(t) * BITS_PER_BYTE) 52 #define BITS_TO_BYTES(n) howmany((n), BITS_PER_BYTE) 53 54 #define hweight8(x) bitcount((uint8_t)(x)) 55 #define hweight16(x) bitcount16(x) 56 #define hweight32(x) bitcount32(x) 57 #define hweight64(x) bitcount64(x) 58 #define hweight_long(x) bitcountl(x) 59 60 #if __has_builtin(__builtin_popcountg) 61 #define HWEIGHT8(x) (__builtin_popcountg((uint8_t)(x))) 62 #define HWEIGHT16(x) (__builtin_popcountg((uint16_t)(x))) 63 #define HWEIGHT32(x) (__builtin_popcountg((uint32_t)(x))) 64 #define HWEIGHT64(x) (__builtin_popcountg((uint64_t)(x))) 65 #else 66 /* LLVM before 19, gcc before 14. */ 67 #define HWEIGHT8(x) (__const_bitcount8((uint8_t)(x))) 68 #define HWEIGHT16(x) (__const_bitcount16((uint16_t)(x))) 69 #define HWEIGHT32(x) (__const_bitcount32((uint32_t)(x))) 70 #define HWEIGHT64(x) (__const_bitcount64((uint64_t)(x))) 71 #endif 72 73 static inline int 74 __ffs(int mask) 75 { 76 return (ffs(mask) - 1); 77 } 78 79 static inline int 80 __fls(int mask) 81 { 82 return (fls(mask) - 1); 83 } 84 85 static inline int 86 __ffsl(long mask) 87 { 88 return (ffsl(mask) - 1); 89 } 90 91 static inline unsigned long 92 __ffs64(uint64_t mask) 93 { 94 return (ffsll(mask) - 1); 95 } 96 97 static inline int 98 __flsl(long mask) 99 { 100 return (flsl(mask) - 1); 101 } 102 103 static inline int 104 fls64(uint64_t mask) 105 { 106 return (flsll(mask)); 107 } 108 109 static inline uint32_t 110 ror32(uint32_t word, unsigned int shift) 111 { 112 return ((word >> shift) | (word << (32 - shift))); 113 } 114 115 #define ffz(mask) __ffs(~(mask)) 116 117 static inline int get_count_order(unsigned int count) 118 { 119 int order; 120 121 order = fls(count) - 1; 122 if (count & (count - 1)) 123 order++; 124 return order; 125 } 126 127 static inline unsigned long 128 find_first_bit(const unsigned long *addr, unsigned long size) 129 { 130 long mask; 131 int bit; 132 133 for (bit = 0; size >= BITS_PER_LONG; 134 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 135 if (*addr == 0) 136 continue; 137 return (bit + __ffsl(*addr)); 138 } 139 if (size) { 140 mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 141 if (mask) 142 bit += __ffsl(mask); 143 else 144 bit += size; 145 } 146 return (bit); 147 } 148 149 static inline unsigned long 150 find_first_zero_bit(const unsigned long *addr, unsigned long size) 151 { 152 long mask; 153 int bit; 154 155 for (bit = 0; size >= BITS_PER_LONG; 156 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 157 if (~(*addr) == 0) 158 continue; 159 return (bit + __ffsl(~(*addr))); 160 } 161 if (size) { 162 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 163 if (mask) 164 bit += __ffsl(mask); 165 else 166 bit += size; 167 } 168 return (bit); 169 } 170 171 static inline unsigned long 172 find_last_bit(const unsigned long *addr, unsigned long size) 173 { 174 long mask; 175 int offs; 176 int bit; 177 int pos; 178 179 pos = size / BITS_PER_LONG; 180 offs = size % BITS_PER_LONG; 181 bit = BITS_PER_LONG * pos; 182 addr += pos; 183 if (offs) { 184 mask = (*addr) & BITMAP_LAST_WORD_MASK(offs); 185 if (mask) 186 return (bit + __flsl(mask)); 187 } 188 while (pos--) { 189 addr--; 190 bit -= BITS_PER_LONG; 191 if (*addr) 192 return (bit + __flsl(*addr)); 193 } 194 return (size); 195 } 196 197 static inline unsigned long 198 find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 199 { 200 long mask; 201 int offs; 202 int bit; 203 int pos; 204 205 if (offset >= size) 206 return (size); 207 pos = offset / BITS_PER_LONG; 208 offs = offset % BITS_PER_LONG; 209 bit = BITS_PER_LONG * pos; 210 addr += pos; 211 if (offs) { 212 mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs); 213 if (mask) 214 return (bit + __ffsl(mask)); 215 if (size - bit <= BITS_PER_LONG) 216 return (size); 217 bit += BITS_PER_LONG; 218 addr++; 219 } 220 for (size -= bit; size >= BITS_PER_LONG; 221 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 222 if (*addr == 0) 223 continue; 224 return (bit + __ffsl(*addr)); 225 } 226 if (size) { 227 mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 228 if (mask) 229 bit += __ffsl(mask); 230 else 231 bit += size; 232 } 233 return (bit); 234 } 235 236 static inline unsigned long 237 find_next_zero_bit(const unsigned long *addr, unsigned long size, 238 unsigned long offset) 239 { 240 long mask; 241 int offs; 242 int bit; 243 int pos; 244 245 if (offset >= size) 246 return (size); 247 pos = offset / BITS_PER_LONG; 248 offs = offset % BITS_PER_LONG; 249 bit = BITS_PER_LONG * pos; 250 addr += pos; 251 if (offs) { 252 mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs); 253 if (mask) 254 return (bit + __ffsl(mask)); 255 if (size - bit <= BITS_PER_LONG) 256 return (size); 257 bit += BITS_PER_LONG; 258 addr++; 259 } 260 for (size -= bit; size >= BITS_PER_LONG; 261 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 262 if (~(*addr) == 0) 263 continue; 264 return (bit + __ffsl(~(*addr))); 265 } 266 if (size) { 267 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 268 if (mask) 269 bit += __ffsl(mask); 270 else 271 bit += size; 272 } 273 return (bit); 274 } 275 276 #define __set_bit(i, a) \ 277 atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 278 279 #define set_bit(i, a) \ 280 atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 281 282 #define __clear_bit(i, a) \ 283 atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 284 285 #define clear_bit(i, a) \ 286 atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 287 288 #define clear_bit_unlock(i, a) \ 289 atomic_clear_rel_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 290 291 #define test_bit(i, a) \ 292 !!(READ_ONCE(((volatile const unsigned long *)(a))[BIT_WORD(i)]) & BIT_MASK(i)) 293 294 static inline void 295 __assign_bit(long bit, volatile unsigned long *addr, bool value) 296 { 297 if (value) 298 __set_bit(bit, addr); 299 else 300 __clear_bit(bit, addr); 301 } 302 303 static inline int 304 test_and_clear_bit(long bit, volatile unsigned long *var) 305 { 306 long val; 307 308 var += BIT_WORD(bit); 309 bit %= BITS_PER_LONG; 310 bit = (1UL << bit); 311 312 val = *var; 313 while (!atomic_fcmpset_long(var, &val, val & ~bit)) 314 ; 315 return !!(val & bit); 316 } 317 318 static inline int 319 __test_and_clear_bit(long bit, volatile unsigned long *var) 320 { 321 long val; 322 323 var += BIT_WORD(bit); 324 bit %= BITS_PER_LONG; 325 bit = (1UL << bit); 326 327 val = *var; 328 *var &= ~bit; 329 330 return !!(val & bit); 331 } 332 333 static inline int 334 test_and_set_bit(long bit, volatile unsigned long *var) 335 { 336 long val; 337 338 var += BIT_WORD(bit); 339 bit %= BITS_PER_LONG; 340 bit = (1UL << bit); 341 342 val = *var; 343 while (!atomic_fcmpset_long(var, &val, val | bit)) 344 ; 345 return !!(val & bit); 346 } 347 348 static inline int 349 __test_and_set_bit(long bit, volatile unsigned long *var) 350 { 351 long val; 352 353 var += BIT_WORD(bit); 354 bit %= BITS_PER_LONG; 355 bit = (1UL << bit); 356 357 val = *var; 358 *var |= bit; 359 360 return !!(val & bit); 361 } 362 363 enum { 364 REG_OP_ISFREE, 365 REG_OP_ALLOC, 366 REG_OP_RELEASE, 367 }; 368 369 static inline int 370 linux_reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 371 { 372 int nbits_reg; 373 int index; 374 int offset; 375 int nlongs_reg; 376 int nbitsinlong; 377 unsigned long mask; 378 int i; 379 int ret = 0; 380 381 nbits_reg = 1 << order; 382 index = pos / BITS_PER_LONG; 383 offset = pos - (index * BITS_PER_LONG); 384 nlongs_reg = BITS_TO_LONGS(nbits_reg); 385 nbitsinlong = MIN(nbits_reg, BITS_PER_LONG); 386 387 mask = (1UL << (nbitsinlong - 1)); 388 mask += mask - 1; 389 mask <<= offset; 390 391 switch (reg_op) { 392 case REG_OP_ISFREE: 393 for (i = 0; i < nlongs_reg; i++) { 394 if (bitmap[index + i] & mask) 395 goto done; 396 } 397 ret = 1; 398 break; 399 400 case REG_OP_ALLOC: 401 for (i = 0; i < nlongs_reg; i++) 402 bitmap[index + i] |= mask; 403 break; 404 405 case REG_OP_RELEASE: 406 for (i = 0; i < nlongs_reg; i++) 407 bitmap[index + i] &= ~mask; 408 break; 409 } 410 done: 411 return ret; 412 } 413 414 #define for_each_set_bit(bit, addr, size) \ 415 for ((bit) = find_first_bit((addr), (size)); \ 416 (bit) < (size); \ 417 (bit) = find_next_bit((addr), (size), (bit) + 1)) 418 419 #define for_each_clear_bit(bit, addr, size) \ 420 for ((bit) = find_first_zero_bit((addr), (size)); \ 421 (bit) < (size); \ 422 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 423 424 static inline uint64_t 425 sign_extend64(uint64_t value, int index) 426 { 427 uint8_t shift = 63 - index; 428 429 return ((int64_t)(value << shift) >> shift); 430 } 431 432 static inline uint32_t 433 sign_extend32(uint32_t value, int index) 434 { 435 uint8_t shift = 31 - index; 436 437 return ((int32_t)(value << shift) >> shift); 438 } 439 440 #endif /* _LINUXKPI_LINUX_BITOPS_H_ */ 441