1219820Sjeff/*- 2219820Sjeff * Copyright (c) 2010 Isilon Systems, Inc. 3219820Sjeff * Copyright (c) 2010 iX Systems, Inc. 4219820Sjeff * Copyright (c) 2010 Panasas, Inc. 5271127Shselasky * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. 6219820Sjeff * All rights reserved. 7219820Sjeff * 8219820Sjeff * Redistribution and use in source and binary forms, with or without 9219820Sjeff * modification, are permitted provided that the following conditions 10219820Sjeff * are met: 11219820Sjeff * 1. Redistributions of source code must retain the above copyright 12219820Sjeff * notice unmodified, this list of conditions, and the following 13219820Sjeff * disclaimer. 14219820Sjeff * 2. Redistributions in binary form must reproduce the above copyright 15219820Sjeff * notice, this list of conditions and the following disclaimer in the 16219820Sjeff * documentation and/or other materials provided with the distribution. 17219820Sjeff * 18219820Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19219820Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20219820Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21219820Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22219820Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23219820Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24219820Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25219820Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26219820Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27219820Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28219820Sjeff */ 29219820Sjeff#ifndef _LINUX_BITOPS_H_ 30219820Sjeff#define _LINUX_BITOPS_H_ 31219820Sjeff 32219820Sjeff#ifdef __LP64__ 33219820Sjeff#define BITS_PER_LONG 64 34219820Sjeff#else 35219820Sjeff#define BITS_PER_LONG 32 36219820Sjeff#endif 37219820Sjeff#define BIT_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 38219820Sjeff#define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 39255932Salfred#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 40219820Sjeff 41271127Shselasky#define BITS_PER_BYTE 8 42271127Shselasky 43219820Sjeffstatic inline int 44219820Sjeff__ffs(int mask) 45219820Sjeff{ 46219820Sjeff return (ffs(mask) - 1); 47219820Sjeff} 48219820Sjeff 49219820Sjeffstatic inline int 50219820Sjeff__fls(int mask) 51219820Sjeff{ 52219820Sjeff return (fls(mask) - 1); 53219820Sjeff} 54219820Sjeff 55219820Sjeffstatic inline int 56219820Sjeff__ffsl(long mask) 57219820Sjeff{ 58219820Sjeff return (ffsl(mask) - 1); 59219820Sjeff} 60219820Sjeff 61219820Sjeffstatic inline int 62219820Sjeff__flsl(long mask) 63219820Sjeff{ 64219820Sjeff return (flsl(mask) - 1); 65219820Sjeff} 66219820Sjeff 67219820Sjeff 68219820Sjeff#define ffz(mask) __ffs(~(mask)) 69219820Sjeff 70255932Salfredstatic inline int get_count_order(unsigned int count) 71255932Salfred{ 72255932Salfred int order; 73255932Salfred 74255932Salfred order = fls(count) - 1; 75255932Salfred if (count & (count - 1)) 76255932Salfred order++; 77255932Salfred return order; 78255932Salfred} 79255932Salfred 80219820Sjeffstatic inline unsigned long 81219820Sjefffind_first_bit(unsigned long *addr, unsigned long size) 82219820Sjeff{ 83219820Sjeff long mask; 84219820Sjeff int bit; 85219820Sjeff 86219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 87219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 88219820Sjeff if (*addr == 0) 89219820Sjeff continue; 90219820Sjeff return (bit + __ffsl(*addr)); 91219820Sjeff } 92219820Sjeff if (size) { 93219820Sjeff mask = (*addr) & BIT_MASK(size); 94219820Sjeff if (mask) 95219820Sjeff bit += __ffsl(mask); 96219820Sjeff else 97219820Sjeff bit += size; 98219820Sjeff } 99219820Sjeff return (bit); 100219820Sjeff} 101219820Sjeff 102219820Sjeffstatic inline unsigned long 103219820Sjefffind_first_zero_bit(unsigned long *addr, unsigned long size) 104219820Sjeff{ 105219820Sjeff long mask; 106219820Sjeff int bit; 107219820Sjeff 108219820Sjeff for (bit = 0; size >= BITS_PER_LONG; 109219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 110219820Sjeff if (~(*addr) == 0) 111219820Sjeff continue; 112219820Sjeff return (bit + __ffsl(~(*addr))); 113219820Sjeff } 114219820Sjeff if (size) { 115219820Sjeff mask = ~(*addr) & BIT_MASK(size); 116219820Sjeff if (mask) 117219820Sjeff bit += __ffsl(mask); 118219820Sjeff else 119219820Sjeff bit += size; 120219820Sjeff } 121219820Sjeff return (bit); 122219820Sjeff} 123219820Sjeff 124219820Sjeffstatic inline unsigned long 125219820Sjefffind_last_bit(unsigned long *addr, unsigned long size) 126219820Sjeff{ 127219820Sjeff long mask; 128219820Sjeff int offs; 129219820Sjeff int bit; 130219820Sjeff int pos; 131219820Sjeff 132219820Sjeff pos = size / BITS_PER_LONG; 133219820Sjeff offs = size % BITS_PER_LONG; 134219820Sjeff bit = BITS_PER_LONG * pos; 135219820Sjeff addr += pos; 136219820Sjeff if (offs) { 137219820Sjeff mask = (*addr) & BIT_MASK(offs); 138219820Sjeff if (mask) 139219820Sjeff return (bit + __flsl(mask)); 140219820Sjeff } 141219820Sjeff while (--pos) { 142219820Sjeff addr--; 143219820Sjeff bit -= BITS_PER_LONG; 144219820Sjeff if (*addr) 145219820Sjeff return (bit + __flsl(mask)); 146219820Sjeff } 147219820Sjeff return (size); 148219820Sjeff} 149219820Sjeff 150219820Sjeffstatic inline unsigned long 151219820Sjefffind_next_bit(unsigned long *addr, unsigned long size, unsigned long offset) 152219820Sjeff{ 153219820Sjeff long mask; 154219820Sjeff int offs; 155219820Sjeff int bit; 156219820Sjeff int pos; 157219820Sjeff 158219820Sjeff if (offset >= size) 159219820Sjeff return (size); 160219820Sjeff pos = offset / BITS_PER_LONG; 161219820Sjeff offs = offset % BITS_PER_LONG; 162219820Sjeff bit = BITS_PER_LONG * pos; 163219820Sjeff addr += pos; 164219820Sjeff if (offs) { 165219820Sjeff mask = (*addr) & ~BIT_MASK(offs); 166219820Sjeff if (mask) 167219820Sjeff return (bit + __ffsl(mask)); 168219820Sjeff bit += BITS_PER_LONG; 169219820Sjeff addr++; 170219820Sjeff } 171219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 172219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 173219820Sjeff if (*addr == 0) 174219820Sjeff continue; 175219820Sjeff return (bit + __ffsl(*addr)); 176219820Sjeff } 177219820Sjeff if (size) { 178219820Sjeff mask = (*addr) & BIT_MASK(size); 179219820Sjeff if (mask) 180219820Sjeff bit += __ffsl(mask); 181219820Sjeff else 182219820Sjeff bit += size; 183219820Sjeff } 184219820Sjeff return (bit); 185219820Sjeff} 186219820Sjeff 187219820Sjeffstatic inline unsigned long 188219820Sjefffind_next_zero_bit(unsigned long *addr, unsigned long size, 189219820Sjeff unsigned long offset) 190219820Sjeff{ 191219820Sjeff long mask; 192219820Sjeff int offs; 193219820Sjeff int bit; 194219820Sjeff int pos; 195219820Sjeff 196219820Sjeff if (offset >= size) 197219820Sjeff return (size); 198219820Sjeff pos = offset / BITS_PER_LONG; 199219820Sjeff offs = offset % BITS_PER_LONG; 200219820Sjeff bit = BITS_PER_LONG * pos; 201219820Sjeff addr += pos; 202219820Sjeff if (offs) { 203219820Sjeff mask = ~(*addr) & ~BIT_MASK(offs); 204219820Sjeff if (mask) 205219820Sjeff return (bit + __ffsl(mask)); 206219820Sjeff bit += BITS_PER_LONG; 207219820Sjeff addr++; 208219820Sjeff } 209219820Sjeff for (size -= bit; size >= BITS_PER_LONG; 210219820Sjeff size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 211219820Sjeff if (~(*addr) == 0) 212219820Sjeff continue; 213219820Sjeff return (bit + __ffsl(~(*addr))); 214219820Sjeff } 215219820Sjeff if (size) { 216219820Sjeff mask = ~(*addr) & BIT_MASK(size); 217219820Sjeff if (mask) 218219820Sjeff bit += __ffsl(mask); 219219820Sjeff else 220219820Sjeff bit += size; 221219820Sjeff } 222219820Sjeff return (bit); 223219820Sjeff} 224219820Sjeff 225219820Sjeffstatic inline void 226219820Sjeffbitmap_zero(unsigned long *addr, int size) 227219820Sjeff{ 228219820Sjeff int len; 229219820Sjeff 230219820Sjeff len = BITS_TO_LONGS(size) * sizeof(long); 231219820Sjeff memset(addr, 0, len); 232219820Sjeff} 233219820Sjeff 234219820Sjeffstatic inline void 235219820Sjeffbitmap_fill(unsigned long *addr, int size) 236219820Sjeff{ 237219820Sjeff int tail; 238219820Sjeff int len; 239219820Sjeff 240219820Sjeff len = (size / BITS_PER_LONG) * sizeof(long); 241219820Sjeff memset(addr, 0xff, len); 242219820Sjeff tail = size & (BITS_PER_LONG - 1); 243219820Sjeff if (tail) 244219820Sjeff addr[size / BITS_PER_LONG] = BIT_MASK(tail); 245219820Sjeff} 246219820Sjeff 247219820Sjeffstatic inline int 248219820Sjeffbitmap_full(unsigned long *addr, int size) 249219820Sjeff{ 250219820Sjeff long mask; 251219820Sjeff int tail; 252219820Sjeff int len; 253219820Sjeff int i; 254219820Sjeff 255219820Sjeff len = size / BITS_PER_LONG; 256219820Sjeff for (i = 0; i < len; i++) 257219820Sjeff if (addr[i] != ~0UL) 258219820Sjeff return (0); 259219820Sjeff tail = size & (BITS_PER_LONG - 1); 260219820Sjeff if (tail) { 261219820Sjeff mask = BIT_MASK(tail); 262219820Sjeff if ((addr[i] & mask) != mask) 263219820Sjeff return (0); 264219820Sjeff } 265219820Sjeff return (1); 266219820Sjeff} 267219820Sjeff 268219820Sjeffstatic inline int 269219820Sjeffbitmap_empty(unsigned long *addr, int size) 270219820Sjeff{ 271219820Sjeff long mask; 272219820Sjeff int tail; 273219820Sjeff int len; 274219820Sjeff int i; 275219820Sjeff 276219820Sjeff len = size / BITS_PER_LONG; 277219820Sjeff for (i = 0; i < len; i++) 278219820Sjeff if (addr[i] != 0) 279219820Sjeff return (0); 280219820Sjeff tail = size & (BITS_PER_LONG - 1); 281219820Sjeff if (tail) { 282219820Sjeff mask = BIT_MASK(tail); 283219820Sjeff if ((addr[i] & mask) != 0) 284219820Sjeff return (0); 285219820Sjeff } 286219820Sjeff return (1); 287219820Sjeff} 288219820Sjeff 289254120Sjeff#define NBLONG (NBBY * sizeof(long)) 290219820Sjeff 291219820Sjeff#define set_bit(i, a) \ 292267517Shselasky atomic_set_long(&((volatile long *)(a))[(i)/NBLONG], 1UL << ((i) % NBLONG)) 293219820Sjeff 294219820Sjeff#define clear_bit(i, a) \ 295267517Shselasky atomic_clear_long(&((volatile long *)(a))[(i)/NBLONG], 1UL << ((i) % NBLONG)) 296219820Sjeff 297219820Sjeff#define test_bit(i, a) \ 298254120Sjeff !!(atomic_load_acq_long(&((volatile long *)(a))[(i)/NBLONG]) & \ 299267517Shselasky (1UL << ((i) % NBLONG))) 300219820Sjeff 301219820Sjeffstatic inline long 302219820Sjefftest_and_clear_bit(long bit, long *var) 303219820Sjeff{ 304219820Sjeff long val; 305219820Sjeff 306254120Sjeff var += bit / (sizeof(long) * NBBY); 307254120Sjeff bit %= sizeof(long) * NBBY; 308267517Shselasky bit = (1UL << bit); 309219820Sjeff do { 310219820Sjeff val = *(volatile long *)var; 311219820Sjeff } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 312219820Sjeff 313219820Sjeff return !!(val & bit); 314219820Sjeff} 315219820Sjeff 316219820Sjeffstatic inline long 317219820Sjefftest_and_set_bit(long bit, long *var) 318219820Sjeff{ 319219820Sjeff long val; 320219820Sjeff 321254120Sjeff var += bit / (sizeof(long) * NBBY); 322254120Sjeff bit %= sizeof(long) * NBBY; 323267517Shselasky bit = (1UL << bit); 324219820Sjeff do { 325219820Sjeff val = *(volatile long *)var; 326219820Sjeff } while (atomic_cmpset_long(var, val, val | bit) == 0); 327219820Sjeff 328219820Sjeff return !!(val & bit); 329219820Sjeff} 330219820Sjeff 331255932Salfred 332255932Salfred#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) 333255932Salfred#define BITMAP_LAST_WORD_MASK(nbits) \ 334255932Salfred( \ 335255932Salfred ((nbits) % BITS_PER_LONG) ? \ 336255932Salfred (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \ 337255932Salfred) 338255932Salfred 339255932Salfred 340255932Salfredstatic inline void 341255932Salfredbitmap_set(unsigned long *map, int start, int nr) 342255932Salfred{ 343255932Salfred unsigned long *p = map + BIT_WORD(start); 344255932Salfred const int size = start + nr; 345255932Salfred int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 346255932Salfred unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 347255932Salfred 348255932Salfred while (nr - bits_to_set >= 0) { 349255932Salfred *p |= mask_to_set; 350255932Salfred nr -= bits_to_set; 351255932Salfred bits_to_set = BITS_PER_LONG; 352255932Salfred mask_to_set = ~0UL; 353255932Salfred p++; 354255932Salfred } 355255932Salfred if (nr) { 356255932Salfred mask_to_set &= BITMAP_LAST_WORD_MASK(size); 357255932Salfred *p |= mask_to_set; 358255932Salfred } 359255932Salfred} 360255932Salfred 361255932Salfredstatic inline void 362255932Salfredbitmap_clear(unsigned long *map, int start, int nr) 363255932Salfred{ 364255932Salfred unsigned long *p = map + BIT_WORD(start); 365255932Salfred const int size = start + nr; 366255932Salfred int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 367255932Salfred unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 368255932Salfred 369255932Salfred while (nr - bits_to_clear >= 0) { 370255932Salfred *p &= ~mask_to_clear; 371255932Salfred nr -= bits_to_clear; 372255932Salfred bits_to_clear = BITS_PER_LONG; 373255932Salfred mask_to_clear = ~0UL; 374255932Salfred p++; 375255932Salfred } 376255932Salfred if (nr) { 377255932Salfred mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 378255932Salfred *p &= ~mask_to_clear; 379255932Salfred } 380255932Salfred} 381255932Salfred 382255932Salfredenum { 383255932Salfred REG_OP_ISFREE, /* true if region is all zero bits */ 384255932Salfred REG_OP_ALLOC, /* set all bits in region */ 385255932Salfred REG_OP_RELEASE, /* clear all bits in region */ 386255932Salfred}; 387255932Salfred 388255932Salfredstatic int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) 389255932Salfred{ 390255932Salfred int nbits_reg; /* number of bits in region */ 391255932Salfred int index; /* index first long of region in bitmap */ 392255932Salfred int offset; /* bit offset region in bitmap[index] */ 393255932Salfred int nlongs_reg; /* num longs spanned by region in bitmap */ 394255932Salfred int nbitsinlong; /* num bits of region in each spanned long */ 395255932Salfred unsigned long mask; /* bitmask for one long of region */ 396255932Salfred int i; /* scans bitmap by longs */ 397255932Salfred int ret = 0; /* return value */ 398255932Salfred 399255932Salfred /* 400255932Salfred * Either nlongs_reg == 1 (for small orders that fit in one long) 401255932Salfred * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) 402255932Salfred */ 403255932Salfred nbits_reg = 1 << order; 404255932Salfred index = pos / BITS_PER_LONG; 405255932Salfred offset = pos - (index * BITS_PER_LONG); 406255932Salfred nlongs_reg = BITS_TO_LONGS(nbits_reg); 407255932Salfred nbitsinlong = min(nbits_reg, BITS_PER_LONG); 408255932Salfred 409255932Salfred /* 410255932Salfred * Can't do "mask = (1UL << nbitsinlong) - 1", as that 411255932Salfred * overflows if nbitsinlong == BITS_PER_LONG. 412255932Salfred */ 413255932Salfred mask = (1UL << (nbitsinlong - 1)); 414255932Salfred mask += mask - 1; 415255932Salfred mask <<= offset; 416255932Salfred 417255932Salfred switch (reg_op) { 418255932Salfred case REG_OP_ISFREE: 419255932Salfred for (i = 0; i < nlongs_reg; i++) { 420255932Salfred if (bitmap[index + i] & mask) 421255932Salfred goto done; 422255932Salfred } 423255932Salfred ret = 1; /* all bits in region free (zero) */ 424255932Salfred break; 425255932Salfred 426255932Salfred case REG_OP_ALLOC: 427255932Salfred for (i = 0; i < nlongs_reg; i++) 428255932Salfred bitmap[index + i] |= mask; 429255932Salfred break; 430255932Salfred 431255932Salfred case REG_OP_RELEASE: 432255932Salfred for (i = 0; i < nlongs_reg; i++) 433255932Salfred bitmap[index + i] &= ~mask; 434255932Salfred break; 435255932Salfred } 436255932Salfreddone: 437255932Salfred return ret; 438255932Salfred} 439255932Salfred 440255932Salfred/** 441255932Salfred * bitmap_find_free_region - find a contiguous aligned mem region 442255932Salfred * @bitmap: array of unsigned longs corresponding to the bitmap 443255932Salfred * @bits: number of bits in the bitmap 444255932Salfred * @order: region size (log base 2 of number of bits) to find 445255932Salfred * 446255932Salfred * Find a region of free (zero) bits in a @bitmap of @bits bits and 447255932Salfred * allocate them (set them to one). Only consider regions of length 448255932Salfred * a power (@order) of two, aligned to that power of two, which 449255932Salfred * makes the search algorithm much faster. 450255932Salfred * 451255932Salfred * Return the bit offset in bitmap of the allocated region, 452255932Salfred * or -errno on failure. 453255932Salfred */ 454255932Salfredstatic inline int 455255932Salfredbitmap_find_free_region(unsigned long *bitmap, int bits, int order) 456255932Salfred{ 457255932Salfred int pos, end; /* scans bitmap by regions of size order */ 458255932Salfred 459255932Salfred for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) { 460255932Salfred if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 461255932Salfred continue; 462255932Salfred __reg_op(bitmap, pos, order, REG_OP_ALLOC); 463255932Salfred return pos; 464255932Salfred } 465255932Salfred return -ENOMEM; 466255932Salfred} 467255932Salfred 468255932Salfred/** 469271127Shselasky * bitmap_allocate_region - allocate bitmap region 470271127Shselasky * @bitmap: array of unsigned longs corresponding to the bitmap 471271127Shselasky * @pos: beginning of bit region to allocate 472271127Shselasky * @order: region size (log base 2 of number of bits) to allocate 473271127Shselasky * 474271127Shselasky * Allocate (set bits in) a specified region of a bitmap. 475271127Shselasky * 476271127Shselasky * Return 0 on success, or %-EBUSY if specified region wasn't 477271127Shselasky * free (not all bits were zero). 478271127Shselasky */ 479271127Shselasky 480271127Shselaskystatic inline int 481271127Shselaskybitmap_allocate_region(unsigned long *bitmap, int pos, int order) 482271127Shselasky{ 483271127Shselasky if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 484271127Shselasky return -EBUSY; 485271127Shselasky __reg_op(bitmap, pos, order, REG_OP_ALLOC); 486271127Shselasky return 0; 487271127Shselasky} 488271127Shselasky 489271127Shselasky/** 490255932Salfred * bitmap_release_region - release allocated bitmap region 491255932Salfred * @bitmap: array of unsigned longs corresponding to the bitmap 492255932Salfred * @pos: beginning of bit region to release 493255932Salfred * @order: region size (log base 2 of number of bits) to release 494255932Salfred * 495255932Salfred * This is the complement to __bitmap_find_free_region() and releases 496255932Salfred * the found region (by clearing it in the bitmap). 497255932Salfred * 498255932Salfred * No return value. 499255932Salfred */ 500255932Salfredstatic inline void 501255932Salfredbitmap_release_region(unsigned long *bitmap, int pos, int order) 502255932Salfred{ 503255932Salfred __reg_op(bitmap, pos, order, REG_OP_RELEASE); 504255932Salfred} 505255932Salfred 506255932Salfred 507271127Shselasky#define for_each_set_bit(bit, addr, size) \ 508271127Shselasky for ((bit) = find_first_bit((addr), (size)); \ 509271127Shselasky (bit) < (size); \ 510271127Shselasky (bit) = find_next_bit((addr), (size), (bit) + 1)) 511271127Shselasky 512219820Sjeff#endif /* _LINUX_BITOPS_H_ */ 513