sys/compat/linuxkpi/common/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  * Copyright (c) 2013-2017 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/param.h>
  35 #include <sys/types.h>
  36 #include <sys/systm.h>
  37 #include <sys/errno.h>
  38 #include <sys/libkern.h>
  39
  40 #define BIT(nr)                 (1UL << (nr))
  41 #define BIT_ULL(nr)             (1ULL << (nr))
  42 #ifdef __LP64__
  43 #define BITS_PER_LONG           64
  44 #else
  45 #define BITS_PER_LONG           32
  46 #endif
  47
  48 #define BITS_PER_LONG_LONG      64
  49
  50 #define BITMAP_FIRST_WORD_MASK(start)   (~0UL << ((start) % BITS_PER_LONG))
  51 #define BITMAP_LAST_WORD_MASK(n)        (~0UL >> (BITS_PER_LONG - (n)))
  52 #define BITS_TO_LONGS(n)        howmany((n), BITS_PER_LONG)
  53 #define BIT_MASK(nr)            (1UL << ((nr) & (BITS_PER_LONG - 1)))
  54 #define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
  55 #define GENMASK(h, l)           (((~0UL) >> (BITS_PER_LONG - (h) - 1)) & ((~0UL) << (l)))
  56 #define GENMASK_ULL(h, l)       (((~0ULL) >> (BITS_PER_LONG_LONG - (h) - 1)) & ((~0ULL) << (l)))
  57 #define BITS_PER_BYTE           8
  58
  59 #define hweight8(x)     bitcount((uint8_t)(x))
  60 #define hweight16(x)    bitcount16(x)
  61 #define hweight32(x)    bitcount32(x)
  62 #define hweight64(x)    bitcount64(x)
  63 #define hweight_long(x) bitcountl(x)
  64
  65 static inline int
  66 __ffs(int mask)
  67 {
  68         return (ffs(mask) - 1);
  69 }
  70
  71 static inline int
  72 __fls(int mask)
  73 {
  74         return (fls(mask) - 1);
  75 }
  76
  77 static inline int
  78 __ffsl(long mask)
  79 {
  80         return (ffsl(mask) - 1);
  81 }
  82
  83 static inline int
  84 __flsl(long mask)
  85 {
  86         return (flsl(mask) - 1);
  87 }
  88
  89 static inline int
  90 fls64(uint64_t mask)
  91 {
  92         return (flsll(mask));
  93 }
  94
  95 static inline uint32_t
  96 ror32(uint32_t word, unsigned int shift)
  97 {
  98         return ((word >> shift) | (word << (32 - shift)));
  99 }
 100
 101 #define ffz(mask)       __ffs(~(mask))
 102
 103 static inline int get_count_order(unsigned int count)
 104 {
 105         int order;
 106
 107         order = fls(count) - 1;
 108         if (count & (count - 1))
 109                 order++;
 110         return order;
 111 }
 112
 113 static inline unsigned long
 114 find_first_bit(const unsigned long *addr, unsigned long size)
 115 {
 116         long mask;
 117         int bit;
 118
 119         for (bit = 0; size >= BITS_PER_LONG;
 120             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
 121                 if (*addr == 0)
 122                         continue;
 123                 return (bit + __ffsl(*addr));
 124         }
 125         if (size) {
 126                 mask = (*addr) & BITMAP_LAST_WORD_MASK(size);
 127                 if (mask)
 128                         bit += __ffsl(mask);
 129                 else
 130                         bit += size;
 131         }
 132         return (bit);
 133 }
 134
 135 static inline unsigned long
 136 find_first_zero_bit(const unsigned long *addr, unsigned long size)
 137 {
 138         long mask;
 139         int bit;
 140
 141         for (bit = 0; size >= BITS_PER_LONG;
 142             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
 143                 if (~(*addr) == 0)
 144                         continue;
 145                 return (bit + __ffsl(~(*addr)));
 146         }
 147         if (size) {
 148                 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size);
 149                 if (mask)
 150                         bit += __ffsl(mask);
 151                 else
 152                         bit += size;
 153         }
 154         return (bit);
 155 }
 156
 157 static inline unsigned long
 158 find_last_bit(const unsigned long *addr, unsigned long size)
 159 {
 160         long mask;
 161         int offs;
 162         int bit;
 163         int pos;
 164
 165         pos = size / BITS_PER_LONG;
 166         offs = size % BITS_PER_LONG;
 167         bit = BITS_PER_LONG * pos;
 168         addr += pos;
 169         if (offs) {
 170                 mask = (*addr) & BITMAP_LAST_WORD_MASK(offs);
 171                 if (mask)
 172                         return (bit + __flsl(mask));
 173         }
 174         while (pos--) {
 175                 addr--;
 176                 bit -= BITS_PER_LONG;
 177                 if (*addr)
 178                         return (bit + __flsl(*addr));
 179         }
 180         return (size);
 181 }
 182
 183 static inline unsigned long
 184 find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset)
 185 {
 186         long mask;
 187         int offs;
 188         int bit;
 189         int pos;
 190
 191         if (offset >= size)
 192                 return (size);
 193         pos = offset / BITS_PER_LONG;
 194         offs = offset % BITS_PER_LONG;
 195         bit = BITS_PER_LONG * pos;
 196         addr += pos;
 197         if (offs) {
 198                 mask = (*addr) & ~BITMAP_LAST_WORD_MASK(offs);
 199                 if (mask)
 200                         return (bit + __ffsl(mask));
 201                 if (size - bit <= BITS_PER_LONG)
 202                         return (size);
 203                 bit += BITS_PER_LONG;
 204                 addr++;
 205         }
 206         for (size -= bit; size >= BITS_PER_LONG;
 207             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
 208                 if (*addr == 0)
 209                         continue;
 210                 return (bit + __ffsl(*addr));
 211         }
 212         if (size) {
 213                 mask = (*addr) & BITMAP_LAST_WORD_MASK(size);
 214                 if (mask)
 215                         bit += __ffsl(mask);
 216                 else
 217                         bit += size;
 218         }
 219         return (bit);
 220 }
 221
 222 static inline unsigned long
 223 find_next_zero_bit(const unsigned long *addr, unsigned long size,
 224     unsigned long offset)
 225 {
 226         long mask;
 227         int offs;
 228         int bit;
 229         int pos;
 230
 231         if (offset >= size)
 232                 return (size);
 233         pos = offset / BITS_PER_LONG;
 234         offs = offset % BITS_PER_LONG;
 235         bit = BITS_PER_LONG * pos;
 236         addr += pos;
 237         if (offs) {
 238                 mask = ~(*addr) & ~BITMAP_LAST_WORD_MASK(offs);
 239                 if (mask)
 240                         return (bit + __ffsl(mask));
 241                 if (size - bit <= BITS_PER_LONG)
 242                         return (size);
 243                 bit += BITS_PER_LONG;
 244                 addr++;
 245         }
 246         for (size -= bit; size >= BITS_PER_LONG;
 247             size -= BITS_PER_LONG, bit += BITS_PER_LONG, addr++) {
 248                 if (~(*addr) == 0)
 249                         continue;
 250                 return (bit + __ffsl(~(*addr)));
 251         }
 252         if (size) {
 253                 mask = ~(*addr) & BITMAP_LAST_WORD_MASK(size);
 254                 if (mask)
 255                         bit += __ffsl(mask);
 256                 else
 257                         bit += size;
 258         }
 259         return (bit);
 260 }
 261
 262 #define __set_bit(i, a)                                                 \
 263     atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i))
 264
 265 #define set_bit(i, a)                                                   \
 266     atomic_set_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i))
 267
 268 #define __clear_bit(i, a)                                               \
 269     atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i))
 270
 271 #define clear_bit(i, a)                                                 \
 272     atomic_clear_long(&((volatile unsigned long *)(a))[BIT_WORD(i)], BIT_MASK(i))
 273
 274 #define test_bit(i, a)                                                  \
 275     !!(READ_ONCE(((volatile unsigned long *)(a))[BIT_WORD(i)]) & BIT_MASK(i))
 276
 277 static inline int
 278 test_and_clear_bit(long bit, volatile unsigned long *var)
 279 {
 280         long val;
 281
 282         var += BIT_WORD(bit);
 283         bit %= BITS_PER_LONG;
 284         bit = (1UL << bit);
 285
 286         val = *var;
 287         while (!atomic_fcmpset_long(var, &val, val & ~bit))
 288                 ;
 289         return !!(val & bit);
 290 }
 291
 292 static inline int
 293 __test_and_clear_bit(long bit, volatile unsigned long *var)
 294 {
 295         long val;
 296
 297         var += BIT_WORD(bit);
 298         bit %= BITS_PER_LONG;
 299         bit = (1UL << bit);
 300
 301         val = *var;
 302         *var &= ~bit;
 303
 304         return !!(val & bit);
 305 }
 306
 307 static inline int
 308 test_and_set_bit(long bit, volatile unsigned long *var)
 309 {
 310         long val;
 311
 312         var += BIT_WORD(bit);
 313         bit %= BITS_PER_LONG;
 314         bit = (1UL << bit);
 315
 316         val = *var;
 317         while (!atomic_fcmpset_long(var, &val, val | bit))
 318                 ;
 319         return !!(val & bit);
 320 }
 321
 322 static inline int
 323 __test_and_set_bit(long bit, volatile unsigned long *var)
 324 {
 325         long val;
 326
 327         var += BIT_WORD(bit);
 328         bit %= BITS_PER_LONG;
 329         bit = (1UL << bit);
 330
 331         val = *var;
 332         *var |= bit;
 333
 334         return !!(val & bit);
 335 }
 336
 337 enum {
 338         REG_OP_ISFREE,
 339         REG_OP_ALLOC,
 340         REG_OP_RELEASE,
 341 };
 342
 343 static inline int
 344 linux_reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
 345 {
 346         int nbits_reg;
 347         int index;
 348         int offset;
 349         int nlongs_reg;
 350         int nbitsinlong;
 351         unsigned long mask;
 352         int i;
 353         int ret = 0;
 354
 355         nbits_reg = 1 << order;
 356         index = pos / BITS_PER_LONG;
 357         offset = pos - (index * BITS_PER_LONG);
 358         nlongs_reg = BITS_TO_LONGS(nbits_reg);
 359         nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
 360
 361         mask = (1UL << (nbitsinlong - 1));
 362         mask += mask - 1;
 363         mask <<= offset;
 364
 365         switch (reg_op) {
 366         case REG_OP_ISFREE:
 367                 for (i = 0; i < nlongs_reg; i++) {
 368                         if (bitmap[index + i] & mask)
 369                                 goto done;
 370                 }
 371                 ret = 1;
 372                 break;
 373
 374         case REG_OP_ALLOC:
 375                 for (i = 0; i < nlongs_reg; i++)
 376                         bitmap[index + i] |= mask;
 377                 break;
 378
 379         case REG_OP_RELEASE:
 380                 for (i = 0; i < nlongs_reg; i++)
 381                         bitmap[index + i] &= ~mask;
 382                 break;
 383         }
 384 done:
 385         return ret;
 386 }
 387
 388 #define for_each_set_bit(bit, addr, size) \
 389         for ((bit) = find_first_bit((addr), (size));            \
 390              (bit) < (size);                                    \
 391              (bit) = find_next_bit((addr), (size), (bit) + 1))
 392
 393 #define for_each_clear_bit(bit, addr, size) \
 394         for ((bit) = find_first_zero_bit((addr), (size));               \
 395              (bit) < (size);                                            \
 396              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
 397
 398 static inline uint64_t
 399 sign_extend64(uint64_t value, int index)
 400 {
 401         uint8_t shift = 63 - index;
 402
 403         return ((int64_t)(value << shift) >> shift);
 404 }
 405
 406 #endif  /* _LINUX_BITOPS_H_ */