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_clear_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 349 val = *var; 350 *var &= ~bit; 351 352 return !!(val & bit); 353 } 354 355 static inline int 356 test_and_set_bit(long bit, volatile unsigned long *var) 357 { 358 long val; 359 360 var += BIT_WORD(bit); 361 bit %= BITS_PER_LONG; 362 bit = (1UL << bit); 363 do { 364 val = *var; 365 } while (atomic_cmpset_long(var, val, val | bit) == 0); 366 367 return !!(val & bit); 368 } 369 370 static inline int 371 __test_and_set_bit(long bit, volatile unsigned long *var) 372 { 373 long val; 374 375 var += BIT_WORD(bit); 376 bit %= BITS_PER_LONG; 377 bit = (1UL << bit); 378 379 val = *var; 380 *var |= bit; 381 382 return !!(val & bit); 383 } 384 385 static inline void 386 bitmap_set(unsigned long *map, int start, int nr) 387 { 388 unsigned long *p = map + BIT_WORD(start); 389 const int size = start + nr; 390 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 391 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 392 393 while (nr - bits_to_set >= 0) { 394 *p |= mask_to_set; 395 nr -= bits_to_set; 396 bits_to_set = BITS_PER_LONG; 397 mask_to_set = ~0UL; 398 p++; 399 } 400 if (nr) { 401 mask_to_set &= BITMAP_LAST_WORD_MASK(size); 402 *p |= mask_to_set; 403 } 404 } 405 406 static inline void 407 bitmap_clear(unsigned long *map, int start, int nr) 408 { 409 unsigned long *p = map + BIT_WORD(start); 410 const int size = start + nr; 411 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 412 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 413 414 while (nr - bits_to_clear >= 0) { 415 *p &= ~mask_to_clear; 416 nr -= bits_to_clear; 417 bits_to_clear = BITS_PER_LONG; 418 mask_to_clear = ~0UL; 419 p++; 420 } 421 if (nr) { 422 mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 423 *p &= ~mask_to_clear; 424 } 425 } 426 427 enum { 428 REG_OP_ISFREE, 429 REG_OP_ALLOC, 430 REG_OP_RELEASE, 431 }; 432 433 static inline int 434 __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 435 { 436 int nbits_reg; 437 int index; 438 int offset; 439 int nlongs_reg; 440 int nbitsinlong; 441 unsigned long mask; 442 int i; 443 int ret = 0; 444 445 nbits_reg = 1 << order; 446 index = pos / BITS_PER_LONG; 447 offset = pos - (index * BITS_PER_LONG); 448 nlongs_reg = BITS_TO_LONGS(nbits_reg); 449 nbitsinlong = min(nbits_reg, BITS_PER_LONG); 450 451 mask = (1UL << (nbitsinlong - 1)); 452 mask += mask - 1; 453 mask <<= offset; 454 455 switch (reg_op) { 456 case REG_OP_ISFREE: 457 for (i = 0; i < nlongs_reg; i++) { 458 if (bitmap[index + i] & mask) 459 goto done; 460 } 461 ret = 1; 462 break; 463 464 case REG_OP_ALLOC: 465 for (i = 0; i < nlongs_reg; i++) 466 bitmap[index + i] |= mask; 467 break; 468 469 case REG_OP_RELEASE: 470 for (i = 0; i < nlongs_reg; i++) 471 bitmap[index + i] &= ~mask; 472 break; 473 } 474 done: 475 return ret; 476 } 477 478 static inline int 479 bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 480 { 481 int pos; 482 int end; 483 484 for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 485 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 486 continue; 487 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 488 return pos; 489 } 490 return -ENOMEM; 491 } 492 493 static inline int 494 bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 495 { 496 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 497 return -EBUSY; 498 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 499 return 0; 500 } 501 502 static inline void 503 bitmap_release_region(unsigned long *bitmap, int pos, int order) 504 { 505 __reg_op(bitmap, pos, order, REG_OP_RELEASE); 506 } 507 508 #define for_each_set_bit(bit, addr, size) \ 509 for ((bit) = find_first_bit((addr), (size)); \ 510 (bit) < (size); \ 511 (bit) = find_next_bit((addr), (size), (bit) + 1)) 512 513 static inline unsigned 514 bitmap_weight(unsigned long *bitmap, unsigned nbits) 515 { 516 unsigned bit; 517 unsigned retval = 0; 518 519 for_each_set_bit(bit, bitmap, nbits) 520 retval++; 521 return (retval); 522 } 523 524 static inline int 525 bitmap_equal(const unsigned long *pa, 526 const unsigned long *pb, unsigned bits) 527 { 528 unsigned x; 529 unsigned y = bits / BITS_PER_LONG; 530 531 for (x = 0; x != y; x++) { 532 if (pa[x] != pb[x]) 533 return (0); 534 } 535 536 y = bits % BITS_PER_LONG; 537 if (y != 0) { 538 if ((pa[x] ^ pb[x]) & BITMAP_LAST_WORD_MASK(y)) 539 return (0); 540 } 541 return (1); 542 } 543 544 #endif /* _LINUX_BITOPS_H_ */ 545