1 /*- 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * Copyright (c) 2015-2016 François Tigeot 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 #ifndef _LINUX_BITOPS_H_ 30 #define _LINUX_BITOPS_H_ 31 32 #include <sys/types.h> 33 #include <sys/systm.h> 34 35 #define BIT(nr) (1UL << (nr)) 36 #ifdef __LP64__ 37 #define BITS_PER_LONG 64 38 #else 39 #define BITS_PER_LONG 32 40 #endif 41 #define BIT_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 42 #define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 43 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 44 45 static inline int 46 __ffs(int mask) 47 { 48 return (ffs(mask) - 1); 49 } 50 51 static inline int 52 __fls(int mask) 53 { 54 return (fls(mask) - 1); 55 } 56 57 static inline int 58 __ffsl(long mask) 59 { 60 return (ffsl(mask) - 1); 61 } 62 63 static inline int 64 __flsl(long mask) 65 { 66 return (flsl(mask) - 1); 67 } 68 69 70 #define ffz(mask) __ffs(~(mask)) 71 72 static inline int get_count_order(unsigned int count) 73 { 74 int order; 75 76 order = fls(count) - 1; 77 if (count & (count - 1)) 78 order++; 79 return order; 80 } 81 82 static inline unsigned long 83 find_first_bit(unsigned long *addr, unsigned long size) 84 { 85 long mask; 86 int bit; 87 88 for (bit = 0; size >= BITS_PER_LONG; 89 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 90 if (*addr == 0) 91 continue; 92 return (bit + __ffsl(*addr)); 93 } 94 if (size) { 95 mask = (*addr) & BIT_MASK(size); 96 if (mask) 97 bit += __ffsl(mask); 98 else 99 bit += size; 100 } 101 return (bit); 102 } 103 104 static inline unsigned long 105 find_first_zero_bit(unsigned long *addr, unsigned long size) 106 { 107 long mask; 108 int bit; 109 110 for (bit = 0; size >= BITS_PER_LONG; 111 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 112 if (~(*addr) == 0) 113 continue; 114 return (bit + __ffsl(~(*addr))); 115 } 116 if (size) { 117 mask = ~(*addr) & BIT_MASK(size); 118 if (mask) 119 bit += __ffsl(mask); 120 else 121 bit += size; 122 } 123 return (bit); 124 } 125 126 static inline unsigned long 127 find_last_bit(unsigned long *addr, unsigned long size) 128 { 129 long mask; 130 int offs; 131 int bit; 132 int pos; 133 134 pos = size / BITS_PER_LONG; 135 offs = size % BITS_PER_LONG; 136 bit = BITS_PER_LONG * pos; 137 addr += pos; 138 if (offs) { 139 mask = (*addr) & BIT_MASK(offs); 140 if (mask) 141 return (bit + __flsl(mask)); 142 } 143 while (--pos) { 144 addr--; 145 bit -= BITS_PER_LONG; 146 if (*addr) 147 return (bit + __flsl(mask)); 148 } 149 return (size); 150 } 151 152 static inline unsigned long 153 find_next_bit(unsigned long *addr, unsigned long size, unsigned long offset) 154 { 155 long mask; 156 int offs; 157 int bit; 158 int pos; 159 160 if (offset >= size) 161 return (size); 162 pos = offset / BITS_PER_LONG; 163 offs = offset % BITS_PER_LONG; 164 bit = BITS_PER_LONG * pos; 165 addr += pos; 166 if (offs) { 167 mask = (*addr) & ~BIT_MASK(offs); 168 if (mask) 169 return (bit + __ffsl(mask)); 170 bit += BITS_PER_LONG; 171 addr++; 172 } 173 for (size -= bit; size >= BITS_PER_LONG; 174 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 175 if (*addr == 0) 176 continue; 177 return (bit + __ffsl(*addr)); 178 } 179 if (size) { 180 mask = (*addr) & BIT_MASK(size); 181 if (mask) 182 bit += __ffsl(mask); 183 else 184 bit += size; 185 } 186 return (bit); 187 } 188 189 static inline unsigned long 190 find_next_zero_bit(unsigned long *addr, unsigned long size, 191 unsigned long offset) 192 { 193 long mask; 194 int offs; 195 int bit; 196 int pos; 197 198 if (offset >= size) 199 return (size); 200 pos = offset / BITS_PER_LONG; 201 offs = offset % BITS_PER_LONG; 202 bit = BITS_PER_LONG * pos; 203 addr += pos; 204 if (offs) { 205 mask = ~(*addr) & ~BIT_MASK(offs); 206 if (mask) 207 return (bit + __ffsl(mask)); 208 bit += BITS_PER_LONG; 209 addr++; 210 } 211 for (size -= bit; size >= BITS_PER_LONG; 212 size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 213 if (~(*addr) == 0) 214 continue; 215 return (bit + __ffsl(~(*addr))); 216 } 217 if (size) { 218 mask = ~(*addr) & BIT_MASK(size); 219 if (mask) 220 bit += __ffsl(mask); 221 else 222 bit += size; 223 } 224 return (bit); 225 } 226 227 static inline void 228 bitmap_zero(unsigned long *addr, int size) 229 { 230 int len; 231 232 len = BITS_TO_LONGS(size) * sizeof(long); 233 memset(addr, 0, len); 234 } 235 236 static inline void 237 bitmap_fill(unsigned long *addr, int size) 238 { 239 int tail; 240 int len; 241 242 len = (size / BITS_PER_LONG) * sizeof(long); 243 memset(addr, 0xff, len); 244 tail = size & (BITS_PER_LONG - 1); 245 if (tail) 246 addr[size / BITS_PER_LONG] = BIT_MASK(tail); 247 } 248 249 static inline int 250 bitmap_full(unsigned long *addr, int size) 251 { 252 long mask; 253 int tail; 254 int len; 255 int i; 256 257 len = size / BITS_PER_LONG; 258 for (i = 0; i < len; i++) 259 if (addr[i] != ~0UL) 260 return (0); 261 tail = size & (BITS_PER_LONG - 1); 262 if (tail) { 263 mask = BIT_MASK(tail); 264 if ((addr[i] & mask) != mask) 265 return (0); 266 } 267 return (1); 268 } 269 270 static inline int 271 bitmap_empty(unsigned long *addr, int size) 272 { 273 long mask; 274 int tail; 275 int len; 276 int i; 277 278 len = size / BITS_PER_LONG; 279 for (i = 0; i < len; i++) 280 if (addr[i] != 0) 281 return (0); 282 tail = size & (BITS_PER_LONG - 1); 283 if (tail) { 284 mask = BIT_MASK(tail); 285 if ((addr[i] & mask) != 0) 286 return (0); 287 } 288 return (1); 289 } 290 291 #define NBLONG (NBBY * sizeof(long)) 292 293 #define set_bit(i, a) \ 294 atomic_set_long(&((volatile long *)(a))[(i)/NBLONG], 1LU << ((i) % NBLONG)) 295 296 #define clear_bit(i, a) \ 297 atomic_clear_long(&((volatile long *)(a))[(i)/NBLONG], 1LU << ((i) % NBLONG)) 298 299 #define test_bit(i, a) \ 300 !!(atomic_load_acq_long(&((volatile long *)(a))[(i)/NBLONG]) & \ 301 (1LU << ((i) % NBLONG))) 302 303 static inline long 304 test_and_clear_bit(long bit, long *var) 305 { 306 long val; 307 308 var += bit / (sizeof(long) * NBBY); 309 bit %= sizeof(long) * NBBY; 310 bit = 1L << bit; 311 do { 312 val = *(volatile long *)var; 313 } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 314 315 return !!(val & bit); 316 } 317 318 static inline unsigned long 319 __test_and_clear_bit(unsigned int bit, volatile unsigned long *ptr) 320 { 321 const unsigned int units = (sizeof(*ptr) * NBBY); 322 volatile unsigned long *const p = &ptr[bit / units]; 323 const unsigned long mask = (1UL << (bit % units)); 324 unsigned long v; 325 326 v = *p; 327 *p &= ~mask; 328 329 return ((v & mask) != 0); 330 } 331 332 static inline long 333 test_and_set_bit(long bit, volatile unsigned long *var) 334 { 335 long val; 336 337 var += bit / (sizeof(long) * NBBY); 338 bit %= sizeof(long) * NBBY; 339 bit = 1L << 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 348 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 349 #define BITMAP_LAST_WORD_MASK(nbits) \ 350 ( \ 351 ((nbits) % BITS_PER_LONG) ? \ 352 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ 353 ) 354 355 356 static inline void 357 bitmap_set(unsigned long *map, int start, int nr) 358 { 359 unsigned long *p = map + BIT_WORD(start); 360 const int size = start + nr; 361 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 362 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 363 364 while (nr - bits_to_set >= 0) { 365 *p |= mask_to_set; 366 nr -= bits_to_set; 367 bits_to_set = BITS_PER_LONG; 368 mask_to_set = ~0UL; 369 p++; 370 } 371 if (nr) { 372 mask_to_set &= BITMAP_LAST_WORD_MASK(size); 373 *p |= mask_to_set; 374 } 375 } 376 377 static inline void 378 bitmap_clear(unsigned long *map, int start, int nr) 379 { 380 unsigned long *p = map + BIT_WORD(start); 381 const int size = start + nr; 382 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 383 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 384 385 while (nr - bits_to_clear >= 0) { 386 *p &= ~mask_to_clear; 387 nr -= bits_to_clear; 388 bits_to_clear = BITS_PER_LONG; 389 mask_to_clear = ~0UL; 390 p++; 391 } 392 if (nr) { 393 mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 394 *p &= ~mask_to_clear; 395 } 396 } 397 398 enum { 399 REG_OP_ISFREE, /* true if region is all zero bits */ 400 REG_OP_ALLOC, /* set all bits in region */ 401 REG_OP_RELEASE, /* clear all bits in region */ 402 }; 403 404 static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 405 { 406 int nbits_reg; /* number of bits in region */ 407 int index; /* index first long of region in bitmap */ 408 int offset; /* bit offset region in bitmap[index] */ 409 int nlongs_reg; /* num longs spanned by region in bitmap */ 410 int nbitsinlong; /* num bits of region in each spanned long */ 411 unsigned long mask; /* bitmask for one long of region */ 412 int i; /* scans bitmap by longs */ 413 int ret = 0; /* return value */ 414 415 /* 416 * Either nlongs_reg == 1 (for small orders that fit in one long) 417 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) 418 */ 419 nbits_reg = 1 << order; 420 index = pos / BITS_PER_LONG; 421 offset = pos - (index * BITS_PER_LONG); 422 nlongs_reg = BITS_TO_LONGS(nbits_reg); 423 nbitsinlong = min(nbits_reg, BITS_PER_LONG); 424 425 /* 426 * Can't do "mask = (1UL << nbitsinlong) - 1", as that 427 * overflows if nbitsinlong == BITS_PER_LONG. 428 */ 429 mask = (1UL << (nbitsinlong - 1)); 430 mask += mask - 1; 431 mask <<= offset; 432 433 switch (reg_op) { 434 case REG_OP_ISFREE: 435 for (i = 0; i < nlongs_reg; i++) { 436 if (bitmap[index + i] & mask) 437 goto done; 438 } 439 ret = 1; /* all bits in region free (zero) */ 440 break; 441 442 case REG_OP_ALLOC: 443 for (i = 0; i < nlongs_reg; i++) 444 bitmap[index + i] |= mask; 445 break; 446 447 case REG_OP_RELEASE: 448 for (i = 0; i < nlongs_reg; i++) 449 bitmap[index + i] &= ~mask; 450 break; 451 } 452 done: 453 return ret; 454 } 455 456 /** 457 * bitmap_find_free_region - find a contiguous aligned mem region 458 * @bitmap: array of unsigned longs corresponding to the bitmap 459 * @bits: number of bits in the bitmap 460 * @order: region size (log base 2 of number of bits) to find 461 * 462 * Find a region of free (zero) bits in a @bitmap of @bits bits and 463 * allocate them (set them to one). Only consider regions of length 464 * a power (@order) of two, aligned to that power of two, which 465 * makes the search algorithm much faster. 466 * 467 * Return the bit offset in bitmap of the allocated region, 468 * or -errno on failure. 469 */ 470 static inline int 471 bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 472 { 473 int pos, end; /* scans bitmap by regions of size order */ 474 475 for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 476 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 477 continue; 478 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 479 return pos; 480 } 481 return -ENOMEM; 482 } 483 484 /** 485 * bitmap_release_region - release allocated bitmap region 486 * @bitmap: array of unsigned longs corresponding to the bitmap 487 * @pos: beginning of bit region to release 488 * @order: region size (log base 2 of number of bits) to release 489 * 490 * This is the complement to __bitmap_find_free_region() and releases 491 * the found region (by clearing it in the bitmap). 492 * 493 * No return value. 494 */ 495 static inline void 496 bitmap_release_region(unsigned long *bitmap, int pos, int order) 497 { 498 __reg_op(bitmap, pos, order, REG_OP_RELEASE); 499 } 500 501 /* Returns a contiguous bitmask from bits h to l */ 502 #define GENMASK(h, l) \ 503 ((~0UL) >> (BITS_PER_LONG - h - 1)) & ((~0UL) << l) 504 505 #include <asm/bitops/non-atomic.h> 506 #include <asm/bitops/const_hweight.h> 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 514 static inline int64_t 515 sign_extend64(uint64_t value, int index) 516 { 517 uint8_t shift = 63 - index; 518 return (int64_t)(value << shift) >> shift; 519 } 520 521 #endif /* _LINUX_BITOPS_H_ */ 522