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