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-2015 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 _LINUX_BITOPS_H_ 32 #define _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 39 #define BIT(nr) (1UL << (nr)) 40 #ifdef __LP64__ 41 #define BITS_PER_LONG 64 42 #else 43 #define BITS_PER_LONG 32 44 #endif 45 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 46 #define BITMAP_LAST_WORD_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 47 #define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 48 #define BIT_MASK(nr) (1UL << ((nr) & (BITS_PER_LONG - 1))) 49 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 50 #define GENMASK(h, l) (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l))) 51 #define BITS_PER_BYTE 8 52 53 static inline int 54 __ffs(int mask) 55 { 56 return (ffs(mask) - 1); 57 } 58 59 static inline int 60 __fls(int mask) 61 { 62 return (fls(mask) - 1); 63 } 64 65 static inline int 66 __ffsl(long mask) 67 { 68 return (ffsl(mask) - 1); 69 } 70 71 static inline int 72 __flsl(long mask) 73 { 74 return (flsl(mask) - 1); 75 } 76 77 static inline uint32_t 78 ror32(uint32_t word, unsigned int shift) 79 { 80 81 return ((word >> shift) | (word << (32 - shift))); 82 } 83 84 #define ffz(mask) __ffs(~(mask)) 85 86 static inline int get_count_order(unsigned int count) 87 { 88 int order; 89 90 order = fls(count) - 1; 91 if (count & (count - 1)) 92 order++; 93 return order; 94 } 95 96 static inline unsigned long 97 find_first_bit(const unsigned long *addr, unsigned long size) 98 { 99 long mask; 100 int bit; 101 102 for (bit = 0; size >= BITS_PER_LONG; 103 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 104 if (*addr == 0) 105 continue; 106 return (bit + __ffsl(*addr)); 107 } 108 if (size) { 109 mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 110 if (mask) 111 bit += __ffsl(mask); 112 else 113 bit += size; 114 } 115 return (bit); 116 } 117 118 static inline unsigned long 119 find_first_zero_bit(const unsigned long *addr, unsigned long size) 120 { 121 long mask; 122 int bit; 123 124 for (bit = 0; size >= BITS_PER_LONG; 125 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 126 if (~(*addr) == 0) 127 continue; 128 return (bit + __ffsl(~(*addr))); 129 } 130 if (size) { 131 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 132 if (mask) 133 bit += __ffsl(mask); 134 else 135 bit += size; 136 } 137 return (bit); 138 } 139 140 static inline unsigned long 141 find_last_bit(const unsigned long *addr, unsigned long size) 142 { 143 long mask; 144 int offs; 145 int bit; 146 int pos; 147 148 pos = size / BITS_PER_LONG; 149 offs = size % BITS_PER_LONG; 150 bit = BITS_PER_LONG * pos; 151 addr += pos; 152 if (offs) { 153 mask = (*addr) & BITMAP_LAST_WORD_MASK(offs); 154 if (mask) 155 return (bit + __flsl(mask)); 156 } 157 while (pos--) { 158 addr--; 159 bit -= BITS_PER_LONG; 160 if (*addr) 161 return (bit + __flsl(*addr)); 162 } 163 return (size); 164 } 165 166 static inline unsigned long 167 find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset) 168 { 169 long mask; 170 int offs; 171 int bit; 172 int pos; 173 174 if (offset >= size) 175 return (size); 176 pos = offset / BITS_PER_LONG; 177 offs = offset % BITS_PER_LONG; 178 bit = BITS_PER_LONG * pos; 179 addr += pos; 180 if (offs) { 181 mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs); 182 if (mask) 183 return (bit + __ffsl(mask)); 184 if (size - bit <= BITS_PER_LONG) 185 return (size); 186 bit += BITS_PER_LONG; 187 addr++; 188 } 189 for (size -= bit; size >= BITS_PER_LONG; 190 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 191 if (*addr == 0) 192 continue; 193 return (bit + __ffsl(*addr)); 194 } 195 if (size) { 196 mask = (*addr) & BITMAP_LAST_WORD_MASK(size); 197 if (mask) 198 bit += __ffsl(mask); 199 else 200 bit += size; 201 } 202 return (bit); 203 } 204 205 static inline unsigned long 206 find_next_zero_bit(const unsigned long *addr, unsigned long size, 207 unsigned long offset) 208 { 209 long mask; 210 int offs; 211 int bit; 212 int pos; 213 214 if (offset >= size) 215 return (size); 216 pos = offset / BITS_PER_LONG; 217 offs = offset % BITS_PER_LONG; 218 bit = BITS_PER_LONG * pos; 219 addr += pos; 220 if (offs) { 221 mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs); 222 if (mask) 223 return (bit + __ffsl(mask)); 224 if (size - bit <= BITS_PER_LONG) 225 return (size); 226 bit += BITS_PER_LONG; 227 addr++; 228 } 229 for (size -= bit; size >= BITS_PER_LONG; 230 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 231 if (~(*addr) == 0) 232 continue; 233 return (bit + __ffsl(~(*addr))); 234 } 235 if (size) { 236 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size); 237 if (mask) 238 bit += __ffsl(mask); 239 else 240 bit += size; 241 } 242 return (bit); 243 } 244 245 static inline void 246 bitmap_zero(unsigned long *addr, int size) 247 { 248 int len; 249 250 len = BITS_TO_LONGS(size) * sizeof(long); 251 memset(addr, 0, len); 252 } 253 254 static inline void 255 bitmap_fill(unsigned long *addr, int size) 256 { 257 int tail; 258 int len; 259 260 len = (size / BITS_PER_LONG) * sizeof(long); 261 memset(addr, 0xff, len); 262 tail = size & (BITS_PER_LONG - 1); 263 if (tail) 264 addr[size / BITS_PER_LONG] = BITMAP_LAST_WORD_MASK(tail); 265 } 266 267 static inline int 268 bitmap_full(unsigned long *addr, int size) 269 { 270 unsigned long mask; 271 int tail; 272 int len; 273 int i; 274 275 len = size / BITS_PER_LONG; 276 for (i = 0; i < len; i++) 277 if (addr[i] != ~0UL) 278 return (0); 279 tail = size & (BITS_PER_LONG - 1); 280 if (tail) { 281 mask = BITMAP_LAST_WORD_MASK(tail); 282 if ((addr[i] & mask) != mask) 283 return (0); 284 } 285 return (1); 286 } 287 288 static inline int 289 bitmap_empty(unsigned long *addr, int size) 290 { 291 unsigned long mask; 292 int tail; 293 int len; 294 int i; 295 296 len = size / BITS_PER_LONG; 297 for (i = 0; i < len; i++) 298 if (addr[i] != 0) 299 return (0); 300 tail = size & (BITS_PER_LONG - 1); 301 if (tail) { 302 mask = BITMAP_LAST_WORD_MASK(tail); 303 if ((addr[i] & mask) != 0) 304 return (0); 305 } 306 return (1); 307 } 308 309 #define __set_bit(i, a) \ 310 atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 311 312 #define set_bit(i, a) \ 313 atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 314 315 #define __clear_bit(i, a) \ 316 atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 317 318 #define clear_bit(i, a) \ 319 atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i)) 320 321 #define test_bit(i, a) \ 322 !!(atomic_load_acq_long(&((volatile unsigned long *)(a))[BIT_WORD(i)]) & \ 323 BIT_MASK(i)) 324 325 static inline int 326 test_and_clear_bit(long bit, volatile unsigned long *var) 327 { 328 long val; 329 330 var += BIT_WORD(bit); 331 bit %= BITS_PER_LONG; 332 bit = (1UL << bit); 333 do { 334 val = *var; 335 } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 336 337 return !!(val & bit); 338 } 339 340 static inline int 341 test_and_set_bit(long bit, volatile unsigned long *var) 342 { 343 long val; 344 345 var += BIT_WORD(bit); 346 bit %= BITS_PER_LONG; 347 bit = (1UL << bit); 348 do { 349 val = *var; 350 } while (atomic_cmpset_long(var, val, val | bit) == 0); 351 352 return !!(val & bit); 353 } 354 355 static inline void 356 bitmap_set(unsigned long *map, int start, int nr) 357 { 358 unsigned long *p = map + BIT_WORD(start); 359 const int size = start + nr; 360 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 361 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 362 363 while (nr - bits_to_set >= 0) { 364 *p |= mask_to_set; 365 nr -= bits_to_set; 366 bits_to_set = BITS_PER_LONG; 367 mask_to_set = ~0UL; 368 p++; 369 } 370 if (nr) { 371 mask_to_set &= BITMAP_LAST_WORD_MASK(size); 372 *p |= mask_to_set; 373 } 374 } 375 376 static inline void 377 bitmap_clear(unsigned long *map, int start, int nr) 378 { 379 unsigned long *p = map + BIT_WORD(start); 380 const int size = start + nr; 381 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 382 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 383 384 while (nr - bits_to_clear >= 0) { 385 *p &= ~mask_to_clear; 386 nr -= bits_to_clear; 387 bits_to_clear = BITS_PER_LONG; 388 mask_to_clear = ~0UL; 389 p++; 390 } 391 if (nr) { 392 mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 393 *p &= ~mask_to_clear; 394 } 395 } 396 397 enum { 398 REG_OP_ISFREE, 399 REG_OP_ALLOC, 400 REG_OP_RELEASE, 401 }; 402 403 static inline int 404 __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 405 { 406 int nbits_reg; 407 int index; 408 int offset; 409 int nlongs_reg; 410 int nbitsinlong; 411 unsigned long mask; 412 int i; 413 int ret = 0; 414 415 nbits_reg = 1 << order; 416 index = pos / BITS_PER_LONG; 417 offset = pos - (index * BITS_PER_LONG); 418 nlongs_reg = BITS_TO_LONGS(nbits_reg); 419 nbitsinlong = min(nbits_reg, BITS_PER_LONG); 420 421 mask = (1UL << (nbitsinlong - 1)); 422 mask += mask - 1; 423 mask <<= offset; 424 425 switch (reg_op) { 426 case REG_OP_ISFREE: 427 for (i = 0; i < nlongs_reg; i++) { 428 if (bitmap[index + i] & mask) 429 goto done; 430 } 431 ret = 1; 432 break; 433 434 case REG_OP_ALLOC: 435 for (i = 0; i < nlongs_reg; i++) 436 bitmap[index + i] |= mask; 437 break; 438 439 case REG_OP_RELEASE: 440 for (i = 0; i < nlongs_reg; i++) 441 bitmap[index + i] &= ~mask; 442 break; 443 } 444 done: 445 return ret; 446 } 447 448 static inline int 449 bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 450 { 451 int pos; 452 int end; 453 454 for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 455 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 456 continue; 457 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 458 return pos; 459 } 460 return -ENOMEM; 461 } 462 463 static inline int 464 bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 465 { 466 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 467 return -EBUSY; 468 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 469 return 0; 470 } 471 472 static inline void 473 bitmap_release_region(unsigned long *bitmap, int pos, int order) 474 { 475 __reg_op(bitmap, pos, order, REG_OP_RELEASE); 476 } 477 478 #define for_each_set_bit(bit, addr, size) \ 479 for ((bit) = find_first_bit((addr), (size)); \ 480 (bit) < (size); \ 481 (bit) = find_next_bit((addr), (size), (bit) + 1)) 482 483 static inline unsigned 484 bitmap_weight(unsigned long *bitmap, unsigned nbits) 485 { 486 unsigned bit; 487 unsigned retval = 0; 488 489 for_each_set_bit(bit, bitmap, nbits) 490 retval++; 491 return (retval); 492 } 493 494 static inline int 495 bitmap_equal(const unsigned long *pa, 496 const unsigned long *pb, unsigned bits) 497 { 498 unsigned x; 499 unsigned y = bits / BITS_PER_LONG; 500 501 for (x = 0; x != y; x++) { 502 if (pa[x] != pb[x]) 503 return (0); 504 } 505 506 y = bits % BITS_PER_LONG; 507 if (y != 0) { 508 if ((pa[x] ^ pb[x]) & BITMAP_LAST_WORD_MASK(y)) 509 return (0); 510 } 511 return (1); 512 } 513 514 #endif /* _LINUX_BITOPS_H_ */ 515