sys/ofed/include/linux/bitops.h

   1 /*-
   2  * Copyright (c) 2010 Isilon Systems, Inc.
   3  * Copyright (c) 2010 iX Systems, Inc.
   4  * Copyright (c) 2010 Panasas, Inc.
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice unmodified, this list of conditions, and the following
  12  *    disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28 #ifndef _LINUX_BITOPS_H_
  29 #define _LINUX_BITOPS_H_
  30
  31 #ifdef __LP64__
  32 #define BITS_PER_LONG           64
  33 #else
  34 #define BITS_PER_LONG           32
  35 #endif
  36 #define BIT_MASK(n)             (~0UL >> (BITS_PER_LONG - (n)))
  37 #define BITS_TO_LONGS(n)        howmany((n), BITS_PER_LONG)
  38
  39 static inline int
  40 __ffs(int mask)
  41 {
  42         return (ffs(mask) - 1);
  43 }
  44
  45 static inline int
  46 __fls(int mask)
  47 {
  48         return (fls(mask) - 1);
  49 }
  50
  51 static inline int
  52 __ffsl(long mask)
  53 {
  54         return (ffsl(mask) - 1);
  55 }
  56
  57 static inline int
  58 __flsl(long mask)
  59 {
  60         return (flsl(mask) - 1);
  61 }
  62
  63
  64 #define ffz(mask)       __ffs(~(mask))
  65
  66 static inline unsigned long
  67 find_first_bit(unsigned long *addr, unsigned long size)
  68 {
  69         long mask;
  70         int bit;
  71
  72         for (bit = 0; size >= BITS_PER_LONG;
  73             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
  74                 if (*addr == 0)
  75                         continue;
  76                 return (bit + __ffsl(*addr));
  77         }
  78         if (size) {
  79                 mask = (*addr) & BIT_MASK(size);
  80                 if (mask)
  81                         bit += __ffsl(mask);
  82                 else
  83                         bit += size;
  84         }
  85         return (bit);
  86 }
  87
  88 static inline unsigned long
  89 find_first_zero_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) & BIT_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_last_bit(unsigned long *addr, unsigned long size)
 112 {
 113         long mask;
 114         int offs;
 115         int bit;
 116         int pos;
 117
 118         pos = size / BITS_PER_LONG;
 119         offs = size % BITS_PER_LONG;
 120         bit = BITS_PER_LONG * pos;
 121         addr += pos;
 122         if (offs) {
 123                 mask = (*addr) & BIT_MASK(offs);
 124                 if (mask)
 125                         return (bit + __flsl(mask));
 126         }
 127         while (--pos) {
 128                 addr--;
 129                 bit -= BITS_PER_LONG;
 130                 if (*addr)
 131                         return (bit + __flsl(mask));
 132         }
 133         return (size);
 134 }
 135
 136 static inline unsigned long
 137 find_next_bit(unsigned long *addr, unsigned long size, unsigned long offset)
 138 {
 139         long mask;
 140         int offs;
 141         int bit;
 142         int pos;
 143
 144         if (offset >= size)
 145                 return (size);
 146         pos = offset / BITS_PER_LONG;
 147         offs = offset % BITS_PER_LONG;
 148         bit = BITS_PER_LONG * pos;
 149         addr += pos;
 150         if (offs) {
 151                 mask = (*addr) & ~BIT_MASK(offs);
 152                 if (mask)
 153                         return (bit + __ffsl(mask));
 154                 bit += BITS_PER_LONG;
 155                 addr++;
 156         }
 157         for (size -= bit; size >= BITS_PER_LONG;
 158             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
 159                 if (*addr == 0)
 160                         continue;
 161                 return (bit + __ffsl(*addr));
 162         }
 163         if (size) {
 164                 mask = (*addr) & BIT_MASK(size);
 165                 if (mask)
 166                         bit += __ffsl(mask);
 167                 else
 168                         bit += size;
 169         }
 170         return (bit);
 171 }
 172
 173 static inline unsigned long
 174 find_next_zero_bit(unsigned long *addr, unsigned long size,
 175     unsigned long offset)
 176 {
 177         long mask;
 178         int offs;
 179         int bit;
 180         int pos;
 181
 182         if (offset >= size)
 183                 return (size);
 184         pos = offset / BITS_PER_LONG;
 185         offs = offset % BITS_PER_LONG;
 186         bit = BITS_PER_LONG * pos;
 187         addr += pos;
 188         if (offs) {
 189                 mask = ~(*addr) & ~BIT_MASK(offs);
 190                 if (mask)
 191                         return (bit + __ffsl(mask));
 192                 bit += BITS_PER_LONG;
 193                 addr++;
 194         }
 195         for (size -= bit; size >= BITS_PER_LONG;
 196             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
 197                 if (~(*addr) == 0)
 198                         continue;
 199                 return (bit + __ffsl(~(*addr)));
 200         }
 201         if (size) {
 202                 mask = ~(*addr) & BIT_MASK(size);
 203                 if (mask)
 204                         bit += __ffsl(mask);
 205                 else
 206                         bit += size;
 207         }
 208         return (bit);
 209 }
 210
 211 static inline void
 212 bitmap_zero(unsigned long *addr, int size)
 213 {
 214         int len;
 215
 216         len = BITS_TO_LONGS(size) * sizeof(long);
 217         memset(addr, 0, len);
 218 }
 219
 220 static inline void
 221 bitmap_fill(unsigned long *addr, int size)
 222 {
 223         int tail;
 224         int len;
 225
 226         len = (size / BITS_PER_LONG) * sizeof(long);
 227         memset(addr, 0xff, len);
 228         tail = size & (BITS_PER_LONG - 1);
 229         if (tail)
 230                 addr[size / BITS_PER_LONG] = BIT_MASK(tail);
 231 }
 232
 233 static inline int
 234 bitmap_full(unsigned long *addr, int size)
 235 {
 236         long mask;
 237         int tail;
 238         int len;
 239         int i;
 240
 241         len = size / BITS_PER_LONG;
 242         for (i = 0; i < len; i++)
 243                 if (addr[i] != ~0UL)
 244                         return (0);
 245         tail = size & (BITS_PER_LONG - 1);
 246         if (tail) {
 247                 mask = BIT_MASK(tail);
 248                 if ((addr[i] & mask) != mask)
 249                         return (0);
 250         }
 251         return (1);
 252 }
 253
 254 static inline int
 255 bitmap_empty(unsigned long *addr, int size)
 256 {
 257         long mask;
 258         int tail;
 259         int len;
 260         int i;
 261
 262         len = size / BITS_PER_LONG;
 263         for (i = 0; i < len; i++)
 264                 if (addr[i] != 0)
 265                         return (0);
 266         tail = size & (BITS_PER_LONG - 1);
 267         if (tail) {
 268                 mask = BIT_MASK(tail);
 269                 if ((addr[i] & mask) != 0)
 270                         return (0);
 271         }
 272         return (1);
 273 }
 274
 275 #define NBINT   (NBBY * sizeof(int))
 276
 277 #define set_bit(i, a)                                                   \
 278     atomic_set_int(&((volatile int *)(a))[(i)/NBINT], 1 << (i) % NBINT)
 279
 280 #define clear_bit(i, a)                                                 \
 281     atomic_clear_int(&((volatile int *)(a))[(i)/NBINT], 1 << (i) % NBINT)
 282
 283 #define test_bit(i, a)                                                  \
 284     !!(atomic_load_acq_int(&((volatile int *)(a))[(i)/NBINT]) & 1 << ((i) % NBINT))
 285
 286 static inline long
 287 test_and_clear_bit(long bit, long *var)
 288 {
 289         long val;
 290
 291         bit = 1 << bit;
 292         do {
 293                 val = *(volatile long *)var;
 294         } while (atomic_cmpset_long(var, val, val & ~bit) == 0);
 295
 296         return !!(val & bit);
 297 }
 298
 299 static inline long
 300 test_and_set_bit(long bit, long *var)
 301 {
 302         long val;
 303
 304         bit = 1 << bit;
 305         do {
 306                 val = *(volatile long *)var;
 307         } while (atomic_cmpset_long(var, val, val | bit) == 0);
 308
 309         return !!(val & bit);
 310 }
 311
 312 #endif  /* _LINUX_BITOPS_H_ */