11556Srgrimes/*- 21556Srgrimes * Copyright (c) 2010 Isilon Systems, Inc. 31556Srgrimes * Copyright (c) 2010 iX Systems, Inc. 41556Srgrimes * Copyright (c) 2010 Panasas, Inc. 51556Srgrimes * All rights reserved. 61556Srgrimes * 71556Srgrimes * Redistribution and use in source and binary forms, with or without 81556Srgrimes * modification, are permitted provided that the following conditions 91556Srgrimes * are met: 101556Srgrimes * 1. Redistributions of source code must retain the above copyright 111556Srgrimes * notice unmodified, this list of conditions, and the following 121556Srgrimes * disclaimer. 131556Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141556Srgrimes * notice, this list of conditions and the following disclaimer in the 151556Srgrimes * documentation and/or other materials provided with the distribution. 161556Srgrimes * 171556Srgrimes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 181556Srgrimes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 191556Srgrimes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 201556Srgrimes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 211556Srgrimes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 221556Srgrimes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231556Srgrimes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241556Srgrimes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251556Srgrimes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 261556Srgrimes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 271556Srgrimes */ 281556Srgrimes#ifndef _LINUX_BITOPS_H_ 291556Srgrimes#define _LINUX_BITOPS_H_ 301556Srgrimes 311556Srgrimes#ifdef __LP64__ 321556Srgrimes#define BITS_PER_LONG 64 331556Srgrimes#else 341556Srgrimes#define BITS_PER_LONG 32 351556Srgrimes#endif 361556Srgrimes#define BIT_MASK(n) (~0UL >> (BITS_PER_LONG - (n))) 371556Srgrimes#define BITS_TO_LONGS(n) howmany((n), BITS_PER_LONG) 381556Srgrimes 3936049Scharnierstatic inline int 4036049Scharnier__ffs(int mask) 4136049Scharnier{ 4236049Scharnier return (ffs(mask) - 1); 4340533Smsmith} 441556Srgrimes 451556Srgrimesstatic inline int 461556Srgrimes__fls(int mask) 471556Srgrimes{ 481556Srgrimes return (fls(mask) - 1); 491556Srgrimes} 501556Srgrimes 511556Srgrimesstatic inline int 521556Srgrimes__ffsl(long mask) 531556Srgrimes{ 541556Srgrimes return (ffsl(mask) - 1); 551556Srgrimes} 561556Srgrimes 571556Srgrimesstatic inline int 581556Srgrimes__flsl(long mask) 591556Srgrimes{ 601556Srgrimes return (flsl(mask) - 1); 611556Srgrimes} 621556Srgrimes 631556Srgrimes 641556Srgrimes#define ffz(mask) __ffs(~(mask)) 651556Srgrimes 661556Srgrimesstatic inline unsigned long 671556Srgrimesfind_first_bit(unsigned long *addr, unsigned long size) 681556Srgrimes{ 691556Srgrimes long mask; 701556Srgrimes int bit; 711556Srgrimes 721556Srgrimes for (bit = 0; size >= BITS_PER_LONG; 731556Srgrimes size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 741556Srgrimes if (*addr == 0) 751556Srgrimes continue; 761556Srgrimes return (bit + __ffsl(*addr)); 771556Srgrimes } 781556Srgrimes if (size) { 791556Srgrimes mask = (*addr) & BIT_MASK(size); 801556Srgrimes if (mask) 811556Srgrimes bit += __ffsl(mask); 821556Srgrimes else 831556Srgrimes bit += size; 841556Srgrimes } 851556Srgrimes return (bit); 861556Srgrimes} 871556Srgrimes 881556Srgrimesstatic inline unsigned long 891556Srgrimesfind_first_zero_bit(unsigned long *addr, unsigned long size) 901556Srgrimes{ 911556Srgrimes long mask; 921556Srgrimes int bit; 931556Srgrimes 941556Srgrimes for (bit = 0; size >= BITS_PER_LONG; 951556Srgrimes size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 961556Srgrimes if (~(*addr) == 0) 971556Srgrimes continue; 981556Srgrimes return (bit + __ffsl(~(*addr))); 991556Srgrimes } 1001556Srgrimes if (size) { 1011556Srgrimes mask = ~(*addr) & BIT_MASK(size); 1021556Srgrimes if (mask) 1031556Srgrimes bit += __ffsl(mask); 1041556Srgrimes else 1051556Srgrimes bit += size; 1061556Srgrimes } 1071556Srgrimes return (bit); 1081556Srgrimes} 1091556Srgrimes 1101556Srgrimesstatic inline unsigned long 1111556Srgrimesfind_last_bit(unsigned long *addr, unsigned long size) 1121556Srgrimes{ 1131556Srgrimes long mask; 1141556Srgrimes int offs; 1151556Srgrimes int bit; 1161556Srgrimes int pos; 1171556Srgrimes 1181556Srgrimes pos = size / BITS_PER_LONG; 1191556Srgrimes offs = size % BITS_PER_LONG; 1201556Srgrimes bit = BITS_PER_LONG * pos; 1211556Srgrimes addr += pos; 1221556Srgrimes if (offs) { 1231556Srgrimes mask = (*addr) & BIT_MASK(offs); 1241556Srgrimes if (mask) 1251556Srgrimes return (bit + __flsl(mask)); 1261556Srgrimes } 1271556Srgrimes while (--pos) { 1281556Srgrimes addr--; 1291556Srgrimes bit -= BITS_PER_LONG; 1301556Srgrimes if (*addr) 1311556Srgrimes return (bit + __flsl(mask)); 1321556Srgrimes } 1331556Srgrimes return (size); 1341556Srgrimes} 1351556Srgrimes 1361556Srgrimesstatic inline unsigned long 1371556Srgrimesfind_next_bit(unsigned long *addr, unsigned long size, unsigned long offset) 1381556Srgrimes{ 1391556Srgrimes long mask; 1401556Srgrimes int offs; 1411556Srgrimes int bit; 1421556Srgrimes int pos; 1431556Srgrimes 1441556Srgrimes if (offset >= size) 1451556Srgrimes return (size); 1461556Srgrimes pos = offset / BITS_PER_LONG; 1471556Srgrimes offs = offset % BITS_PER_LONG; 1481556Srgrimes bit = BITS_PER_LONG * pos; 1491556Srgrimes addr += pos; 1501556Srgrimes if (offs) { 1511556Srgrimes mask = (*addr) & ~BIT_MASK(offs); 1521556Srgrimes if (mask) 1531556Srgrimes return (bit + __ffsl(mask)); 1541556Srgrimes bit += BITS_PER_LONG; 1551556Srgrimes addr++; 1561556Srgrimes } 1571556Srgrimes for (size -= bit; size >= BITS_PER_LONG; 1581556Srgrimes size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 1591556Srgrimes if (*addr == 0) 1601556Srgrimes continue; 1611556Srgrimes return (bit + __ffsl(*addr)); 1621556Srgrimes } 1631556Srgrimes if (size) { 1641556Srgrimes mask = (*addr) & BIT_MASK(size); 1651556Srgrimes if (mask) 1661556Srgrimes bit += __ffsl(mask); 1671556Srgrimes else 1681556Srgrimes bit += size; 1691556Srgrimes } 1701556Srgrimes return (bit); 1711556Srgrimes} 1721556Srgrimes 1731556Srgrimesstatic inline unsigned long 1741556Srgrimesfind_next_zero_bit(unsigned long *addr, unsigned long size, 1751556Srgrimes unsigned long offset) 1761556Srgrimes{ 1771556Srgrimes long mask; 1781556Srgrimes int offs; 1791556Srgrimes int bit; 1801556Srgrimes int pos; 1811556Srgrimes 1821556Srgrimes if (offset >= size) 1831556Srgrimes return (size); 1841556Srgrimes pos = offset / BITS_PER_LONG; 1858855Srgrimes offs = offset % BITS_PER_LONG; 1861556Srgrimes bit = BITS_PER_LONG * pos; 1871556Srgrimes addr += pos; 1881556Srgrimes if (offs) { 1891556Srgrimes mask = ~(*addr) & ~BIT_MASK(offs); 1901556Srgrimes if (mask) 1911556Srgrimes return (bit + __ffsl(mask)); 1921556Srgrimes bit += BITS_PER_LONG; 1931556Srgrimes addr++; 1941556Srgrimes } 1951556Srgrimes for (size -= bit; size >= BITS_PER_LONG; 1961556Srgrimes size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) { 1971556Srgrimes if (~(*addr) == 0) 1981556Srgrimes continue; 1991556Srgrimes return (bit + __ffsl(~(*addr))); 2001556Srgrimes } 2011556Srgrimes if (size) { 2021556Srgrimes mask = ~(*addr) & BIT_MASK(size); 2031556Srgrimes if (mask) 2041556Srgrimes bit += __ffsl(mask); 2051556Srgrimes else 2061556Srgrimes bit += size; 2071556Srgrimes } 2081556Srgrimes return (bit); 2091556Srgrimes} 2101556Srgrimes 2111556Srgrimesstatic inline void 2121556Srgrimesbitmap_zero(unsigned long *addr, int size) 2131556Srgrimes{ 2141556Srgrimes int len; 2151556Srgrimes 2161556Srgrimes len = BITS_TO_LONGS(size) * sizeof(long); 2171556Srgrimes memset(addr, 0, len); 2181556Srgrimes} 2191556Srgrimes 2201556Srgrimesstatic inline void 2211556Srgrimesbitmap_fill(unsigned long *addr, int size) 2221556Srgrimes{ 2231556Srgrimes int tail; 2241556Srgrimes int len; 2251556Srgrimes 2261556Srgrimes len = (size / BITS_PER_LONG) * sizeof(long); 2271556Srgrimes memset(addr, 0xff, len); 2281556Srgrimes tail = size & (BITS_PER_LONG - 1); 2291556Srgrimes if (tail) 2301556Srgrimes addr[size / BITS_PER_LONG] = BIT_MASK(tail); 2311556Srgrimes} 2321556Srgrimes 2331556Srgrimesstatic inline int 2341556Srgrimesbitmap_full(unsigned long *addr, int size) 2351556Srgrimes{ 2361556Srgrimes long mask; 2371556Srgrimes int tail; 2381556Srgrimes int len; 2391556Srgrimes int i; 2401556Srgrimes 2411556Srgrimes len = size / BITS_PER_LONG; 2421556Srgrimes for (i = 0; i < len; i++) 2431556Srgrimes if (addr[i] != ~0UL) 2441556Srgrimes return (0); 2451556Srgrimes tail = size & (BITS_PER_LONG - 1); 2461556Srgrimes if (tail) { 2471556Srgrimes mask = BIT_MASK(tail); 2481556Srgrimes if ((addr[i] & mask) != mask) 2498855Srgrimes return (0); 2501556Srgrimes } 2511556Srgrimes return (1); 2521556Srgrimes} 2531556Srgrimes 2541556Srgrimesstatic inline int 2551556Srgrimesbitmap_empty(unsigned long *addr, int size) 2561556Srgrimes{ 2571556Srgrimes long mask; 2581556Srgrimes int tail; 2591556Srgrimes int len; 2601556Srgrimes int i; 2611556Srgrimes 2621556Srgrimes len = size / BITS_PER_LONG; 2631556Srgrimes for (i = 0; i < len; i++) 2641556Srgrimes if (addr[i] != 0) 2651556Srgrimes return (0); 2661556Srgrimes tail = size & (BITS_PER_LONG - 1); 2671556Srgrimes if (tail) { 2681556Srgrimes mask = BIT_MASK(tail); 2691556Srgrimes if ((addr[i] & mask) != 0) 2701556Srgrimes return (0); 2711556Srgrimes } 2721556Srgrimes return (1); 2731556Srgrimes} 2741556Srgrimes 2751556Srgrimes#define NBLONG (NBBY * sizeof(long)) 2761556Srgrimes 2771556Srgrimes#define set_bit(i, a) \ 2781556Srgrimes atomic_set_long(&((volatile long *)(a))[(i)/NBLONG], 1UL << ((i) % NBLONG)) 2791556Srgrimes 2801556Srgrimes#define clear_bit(i, a) \ 2811556Srgrimes atomic_clear_long(&((volatile long *)(a))[(i)/NBLONG], 1UL << ((i) % NBLONG)) 2821556Srgrimes 2831556Srgrimes#define test_bit(i, a) \ 2841556Srgrimes !!(atomic_load_acq_long(&((volatile long *)(a))[(i)/NBLONG]) & \ 2851556Srgrimes (1UL << ((i) % NBLONG))) 2861556Srgrimes 2871556Srgrimesstatic inline long 2881556Srgrimestest_and_clear_bit(long bit, long *var) 2891556Srgrimes{ 2901556Srgrimes long val; 2911556Srgrimes 2921556Srgrimes var += bit / (sizeof(long) * NBBY); 2931556Srgrimes bit %= sizeof(long) * NBBY; 2941556Srgrimes bit = (1UL << bit); 2951556Srgrimes do { 2961556Srgrimes val = *(volatile long *)var; 2971556Srgrimes } while (atomic_cmpset_long(var, val, val & ~bit) == 0); 2981556Srgrimes 2991556Srgrimes return !!(val & bit); 3001556Srgrimes} 3011556Srgrimes 3021556Srgrimesstatic inline long 3031556Srgrimestest_and_set_bit(long bit, long *var) 3041556Srgrimes{ 3051556Srgrimes long val; 3061556Srgrimes 3071556Srgrimes var += bit / (sizeof(long) * NBBY); 3081556Srgrimes bit %= sizeof(long) * NBBY; 3091556Srgrimes bit = (1UL << bit); 3101556Srgrimes do { 3111556Srgrimes val = *(volatile long *)var; 3121556Srgrimes } while (atomic_cmpset_long(var, val, val | bit) == 0); 3131556Srgrimes 3141556Srgrimes return !!(val & bit); 3151556Srgrimes} 3161556Srgrimes 3171556Srgrimes#endif /* _LINUX_BITOPS_H_ */ 3188855Srgrimes