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