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 #ifdef __LP64__ 41 #define BITS_PER_LONG 64 42 #else 43 #define BITS_PER_LONG 32 44 #endif 45 46 #define BITS_PER_LONG_LONG 64 47 48 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 49 #define BITMAP_LAST_WORD_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 50 #define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 51 #define BIT_MASK(nr) (1UL << ((nr) & (BITS_PER_LONG - 1))) 52 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 53 #define GENMASK(h, l) (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l))) 54 #define GENMASK_ULL(h, l) (((~0ULL) >> (BITS_PER_LONG_LONG - (h) - 1)) & ((~0ULL) << (l))) 55 #define BITS_PER_BYTE 8 56 #define BITS_PER_TYPE(t) (sizeof(t) * BITS_PER_BYTE) 57 58 #define hweight8(x) bitcount((uint8_t)(x)) 59 #define hweight16(x) bitcount16(x) 60 #define hweight32(x) bitcount32(x) 61 #define hweight64(x) bitcount64(x) 62 #define hweight_long(x) bitcountl(x) 63 64 #define HWEIGHT8(x) (bitcount8((uint8_t)(x)) + 1) 65 #define HWEIGHT16(x) (bitcount16(x) + 1) 66 #define HWEIGHT32(x) (bitcount32(x) + 1) 67 #define HWEIGHT64(x) (bitcount64(x) + 1) 68 69 static inline int 70 __ffs(int mask) 71 { 72 return (ffs(mask) - 1); 73 } 74 75 static inline int 76 __fls(int mask) 77 { 78 return (fls(mask) - 1); 79 } 80 81 static inline int 82 __ffsl(long mask) 83 { 84 return (ffsl(mask) - 1); 85 } 86 87 static inline unsigned long 88 __ffs64(uint64_t mask) 89 { 90 return (ffsll(mask) - 1); 91 } 92 93 static inline int 94 __flsl(long mask) 95 { 96 return (flsl(mask) - 1); 97 } 98 99 static inline int 100 fls64(uint64_t mask) 101 { 102 return (flsll(mask)); 103 } 104 105 static inline uint32_t 106 ror32(uint32_t word, unsigned int shift) 107 { 108 return ((word >> shift) | (word << (32 - shift))); 109 } 110 111 #define ffz(mask) __ffs(~(mask)) 112 113 static inline int get_count_order(unsigned int count) 114 { 115 int order; 116 117 order = fls(count) - 1; 118 if (count & (count - 1)) 119 order++; 120 return order; 121 } 122 123 static inline unsigned long 124 find_first_bit(const unsigned long *addr, unsigned long size) 125 { 126 long mask; 127 int bit; 128 129 for (bit = 0; size >= BITS_PER_LONG; 130 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 131 if (*addr == 0) 132 continue; 133 return (bit + __ffsl(*addr)); 134 } 135 if (size) { 136 mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 137 if (mask) 138 bit += __ffsl(mask); 139 else 140 bit += size; 141 } 142 return (bit); 143 } 144 145 static inline unsigned long 146 find_first_zero_bit(const unsigned long *addr, unsigned long size) 147 { 148 long mask; 149 int bit; 150 151 for (bit = 0; size >= BITS_PER_LONG; 152 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 153 if (~(*addr) == 0) 154 continue; 155 return (bit + __ffsl(~(*addr))); 156 } 157 if (size) { 158 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 159 if (mask) 160 bit += __ffsl(mask); 161 else 162 bit += size; 163 } 164 return (bit); 165 } 166 167 static inline unsigned long 168 find_last_bit(const unsigned long *addr, unsigned long size) 169 { 170 long mask; 171 int offs; 172 int bit; 173 int pos; 174 175 pos = size / BITS_PER_LONG; 176 offs = size % BITS_PER_LONG; 177 bit = BITS_PER_LONG * pos; 178 addr += pos; 179 if (offs) { 180 mask = (*addr) & BITMAP_LAST_WORD_MASK(offs); 181 if (mask) 182 return (bit + __flsl(mask)); 183 } 184 while (pos--) { 185 addr--; 186 bit -= BITS_PER_LONG; 187 if (*addr) 188 return (bit + __flsl(*addr)); 189 } 190 return (size); 191 } 192 193 static inline unsigned long 194 find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 195 { 196 long mask; 197 int offs; 198 int bit; 199 int pos; 200 201 if (offset >= size) 202 return (size); 203 pos = offset / BITS_PER_LONG; 204 offs = offset % BITS_PER_LONG; 205 bit = BITS_PER_LONG * pos; 206 addr += pos; 207 if (offs) { 208 mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs); 209 if (mask) 210 return (bit + __ffsl(mask)); 211 if (size - bit <= BITS_PER_LONG) 212 return (size); 213 bit += BITS_PER_LONG; 214 addr++; 215 } 216 for (size -= bit; size >= BITS_PER_LONG; 217 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 218 if (*addr == 0) 219 continue; 220 return (bit + __ffsl(*addr)); 221 } 222 if (size) { 223 mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 224 if (mask) 225 bit += __ffsl(mask); 226 else 227 bit += size; 228 } 229 return (bit); 230 } 231 232 static inline unsigned long 233 find_next_zero_bit(const unsigned long *addr, unsigned long size, 234 unsigned long offset) 235 { 236 long mask; 237 int offs; 238 int bit; 239 int pos; 240 241 if (offset >= size) 242 return (size); 243 pos = offset / BITS_PER_LONG; 244 offs = offset % BITS_PER_LONG; 245 bit = BITS_PER_LONG * pos; 246 addr += pos; 247 if (offs) { 248 mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs); 249 if (mask) 250 return (bit + __ffsl(mask)); 251 if (size - bit <= BITS_PER_LONG) 252 return (size); 253 bit += BITS_PER_LONG; 254 addr++; 255 } 256 for (size -= bit; size >= BITS_PER_LONG; 257 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 258 if (~(*addr) == 0) 259 continue; 260 return (bit + __ffsl(~(*addr))); 261 } 262 if (size) { 263 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 264 if (mask) 265 bit += __ffsl(mask); 266 else 267 bit += size; 268 } 269 return (bit); 270 } 271 272 #define __set_bit(i, a) \ 273 atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 274 275 #define set_bit(i, a) \ 276 atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 277 278 #define __clear_bit(i, a) \ 279 atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 280 281 #define clear_bit(i, a) \ 282 atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 283 284 #define clear_bit_unlock(i, a) \ 285 atomic_clear_rel_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 286 287 #define test_bit(i, a) \ 288 !!(READ_ONCE(((volatile const unsigned long *)(a))[BIT_WORD(i)]) & BIT_MASK(i)) 289 290 static inline int 291 test_and_clear_bit(long bit, volatile unsigned long *var) 292 { 293 long val; 294 295 var += BIT_WORD(bit); 296 bit %= BITS_PER_LONG; 297 bit = (1UL << bit); 298 299 val = *var; 300 while (!atomic_fcmpset_long(var, &val, val & ~bit)) 301 ; 302 return !!(val & bit); 303 } 304 305 static inline int 306 __test_and_clear_bit(long bit, volatile unsigned long *var) 307 { 308 long val; 309 310 var += BIT_WORD(bit); 311 bit %= BITS_PER_LONG; 312 bit = (1UL << bit); 313 314 val = *var; 315 *var &= ~bit; 316 317 return !!(val & bit); 318 } 319 320 static inline int 321 test_and_set_bit(long bit, volatile unsigned long *var) 322 { 323 long val; 324 325 var += BIT_WORD(bit); 326 bit %= BITS_PER_LONG; 327 bit = (1UL << bit); 328 329 val = *var; 330 while (!atomic_fcmpset_long(var, &val, val | bit)) 331 ; 332 return !!(val & bit); 333 } 334 335 static inline int 336 __test_and_set_bit(long bit, volatile unsigned long *var) 337 { 338 long val; 339 340 var += BIT_WORD(bit); 341 bit %= BITS_PER_LONG; 342 bit = (1UL << bit); 343 344 val = *var; 345 *var |= bit; 346 347 return !!(val & bit); 348 } 349 350 enum { 351 REG_OP_ISFREE, 352 REG_OP_ALLOC, 353 REG_OP_RELEASE, 354 }; 355 356 static inline int 357 linux_reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 358 { 359 int nbits_reg; 360 int index; 361 int offset; 362 int nlongs_reg; 363 int nbitsinlong; 364 unsigned long mask; 365 int i; 366 int ret = 0; 367 368 nbits_reg = 1 << order; 369 index = pos / BITS_PER_LONG; 370 offset = pos - (index * BITS_PER_LONG); 371 nlongs_reg = BITS_TO_LONGS(nbits_reg); 372 nbitsinlong = MIN(nbits_reg, BITS_PER_LONG); 373 374 mask = (1UL << (nbitsinlong - 1)); 375 mask += mask - 1; 376 mask <<= offset; 377 378 switch (reg_op) { 379 case REG_OP_ISFREE: 380 for (i = 0; i < nlongs_reg; i++) { 381 if (bitmap[index + i] & mask) 382 goto done; 383 } 384 ret = 1; 385 break; 386 387 case REG_OP_ALLOC: 388 for (i = 0; i < nlongs_reg; i++) 389 bitmap[index + i] |= mask; 390 break; 391 392 case REG_OP_RELEASE: 393 for (i = 0; i < nlongs_reg; i++) 394 bitmap[index + i] &= ~mask; 395 break; 396 } 397 done: 398 return ret; 399 } 400 401 #define for_each_set_bit(bit, addr, size) \ 402 for ((bit) = find_first_bit((addr), (size)); \ 403 (bit) < (size); \ 404 (bit) = find_next_bit((addr), (size), (bit) + 1)) 405 406 #define for_each_clear_bit(bit, addr, size) \ 407 for ((bit) = find_first_zero_bit((addr), (size)); \ 408 (bit) < (size); \ 409 (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) 410 411 static inline uint64_t 412 sign_extend64(uint64_t value, int index) 413 { 414 uint8_t shift = 63 - index; 415 416 return ((int64_t)(value << shift) >> shift); 417 } 418 419 static inline uint32_t 420 sign_extend32(uint32_t value, int index) 421 { 422 uint8_t shift = 31 - index; 423 424 return ((int32_t)(value << shift) >> shift); 425 } 426 427 #endif /* _LINUXKPI_LINUX_BITOPS_H_ */ 428