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