sys/compat/linuxkpi/common/include/linux/bitmap.h

   1 /*
   2  * Copyright (c) 2013-2017 Mellanox Technologies, Ltd.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice unmodified, this list of conditions, and the following
  10  *    disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  */
  28
  29 #ifndef _LINUXKPI_LINUX_BITMAP_H_
  30 #define _LINUXKPI_LINUX_BITMAP_H_
  31
  32 #include <linux/bitops.h>
  33 #include <linux/slab.h>
  34
  35 static inline void
  36 bitmap_zero(unsigned long *addr, const unsigned int size)
  37 {
  38         memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
  39 }
  40
  41 static inline void
  42 bitmap_fill(unsigned long *addr, const unsigned int size)
  43 {
  44         const unsigned int tail = size & (BITS_PER_LONG - 1);
  45
  46         memset(addr, 0xff, BIT_WORD(size) * sizeof(long));
  47
  48         if (tail)
  49                 addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
  50 }
  51
  52 static inline int
  53 bitmap_full(unsigned long *addr, const unsigned int size)
  54 {
  55         const unsigned int end = BIT_WORD(size);
  56         const unsigned int tail = size & (BITS_PER_LONG - 1);
  57         unsigned int i;
  58
  59         for (i = 0; i != end; i++) {
  60                 if (addr[i] != ~0UL)
  61                         return (0);
  62         }
  63
  64         if (tail) {
  65                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
  66
  67                 if ((addr[end] & mask) != mask)
  68                         return (0);
  69         }
  70         return (1);
  71 }
  72
  73 static inline int
  74 bitmap_empty(unsigned long *addr, const unsigned int size)
  75 {
  76         const unsigned int end = BIT_WORD(size);
  77         const unsigned int tail = size & (BITS_PER_LONG - 1);
  78         unsigned int i;
  79
  80         for (i = 0; i != end; i++) {
  81                 if (addr[i] != 0)
  82                         return (0);
  83         }
  84
  85         if (tail) {
  86                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
  87
  88                 if ((addr[end] & mask) != 0)
  89                         return (0);
  90         }
  91         return (1);
  92 }
  93
  94 static inline void
  95 bitmap_set(unsigned long *map, unsigned int start, int nr)
  96 {
  97         const unsigned int size = start + nr;
  98         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  99         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 100
 101         map += BIT_WORD(start);
 102
 103         while (nr - bits_to_set >= 0) {
 104                 *map |= mask_to_set;
 105                 nr -= bits_to_set;
 106                 bits_to_set = BITS_PER_LONG;
 107                 mask_to_set = ~0UL;
 108                 map++;
 109         }
 110
 111         if (nr) {
 112                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 113                 *map |= mask_to_set;
 114         }
 115 }
 116
 117 static inline void
 118 bitmap_clear(unsigned long *map, unsigned int start, int nr)
 119 {
 120         const unsigned int size = start + nr;
 121         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 122         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 123
 124         map += BIT_WORD(start);
 125
 126         while (nr - bits_to_clear >= 0) {
 127                 *map &= ~mask_to_clear;
 128                 nr -= bits_to_clear;
 129                 bits_to_clear = BITS_PER_LONG;
 130                 mask_to_clear = ~0UL;
 131                 map++;
 132         }
 133
 134         if (nr) {
 135                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 136                 *map &= ~mask_to_clear;
 137         }
 138 }
 139
 140 static inline unsigned int
 141 bitmap_find_next_zero_area_off(const unsigned long *map,
 142     const unsigned int size, unsigned int start,
 143     unsigned int nr, unsigned int align_mask,
 144     unsigned int align_offset)
 145 {
 146         unsigned int index;
 147         unsigned int end;
 148         unsigned int i;
 149
 150 retry:
 151         index = find_next_zero_bit(map, size, start);
 152
 153         index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;
 154
 155         end = index + nr;
 156         if (end > size)
 157                 return (end);
 158
 159         i = find_next_bit(map, end, index);
 160         if (i < end) {
 161                 start = i + 1;
 162                 goto retry;
 163         }
 164         return (index);
 165 }
 166
 167 static inline unsigned int
 168 bitmap_find_next_zero_area(const unsigned long *map,
 169     const unsigned int size, unsigned int start,
 170     unsigned int nr, unsigned int align_mask)
 171 {
 172         return (bitmap_find_next_zero_area_off(map, size,
 173             start, nr, align_mask, 0));
 174 }
 175
 176 static inline int
 177 bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 178 {
 179         int pos;
 180         int end;
 181
 182         for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
 183                 if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
 184                         continue;
 185                 linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
 186                 return (pos);
 187         }
 188         return (-ENOMEM);
 189 }
 190
 191 static inline int
 192 bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 193 {
 194         if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
 195                 return (-EBUSY);
 196         linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
 197         return (0);
 198 }
 199
 200 static inline void
 201 bitmap_release_region(unsigned long *bitmap, int pos, int order)
 202 {
 203         linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
 204 }
 205
 206 static inline unsigned int
 207 bitmap_weight(unsigned long *addr, const unsigned int size)
 208 {
 209         const unsigned int end = BIT_WORD(size);
 210         const unsigned int tail = size & (BITS_PER_LONG - 1);
 211         unsigned int retval = 0;
 212         unsigned int i;
 213
 214         for (i = 0; i != end; i++)
 215                 retval += hweight_long(addr[i]);
 216
 217         if (tail) {
 218                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
 219
 220                 retval += hweight_long(addr[end] & mask);
 221         }
 222         return (retval);
 223 }
 224
 225 static inline int
 226 bitmap_equal(const unsigned long *pa,
 227     const unsigned long *pb, unsigned size)
 228 {
 229         const unsigned int end = BIT_WORD(size);
 230         const unsigned int tail = size & (BITS_PER_LONG - 1);
 231         unsigned int i;
 232
 233         for (i = 0; i != end; i++) {
 234                 if (pa[i] != pb[i])
 235                         return (0);
 236         }
 237
 238         if (tail) {
 239                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
 240
 241                 if ((pa[end] ^ pb[end]) & mask)
 242                         return (0);
 243         }
 244         return (1);
 245 }
 246
 247 static inline int
 248 bitmap_subset(const unsigned long *pa,
 249     const unsigned long *pb, unsigned size)
 250 {
 251         const unsigned end = BIT_WORD(size);
 252         const unsigned tail = size & (BITS_PER_LONG - 1);
 253         unsigned i;
 254
 255         for (i = 0; i != end; i++) {
 256                 if (pa[i] & ~pb[i])
 257                         return (0);
 258         }
 259
 260         if (tail) {
 261                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
 262
 263                 if (pa[end] & ~pb[end] & mask)
 264                         return (0);
 265         }
 266         return (1);
 267 }
 268
 269 static inline void
 270 bitmap_complement(unsigned long *dst, const unsigned long *src,
 271     const unsigned int size)
 272 {
 273         const unsigned int end = BITS_TO_LONGS(size);
 274         unsigned int i;
 275
 276         for (i = 0; i != end; i++)
 277                 dst[i] = ~src[i];
 278 }
 279
 280 static inline void
 281 bitmap_copy(unsigned long *dst, const unsigned long *src,
 282     const unsigned int size)
 283 {
 284         const unsigned int end = BITS_TO_LONGS(size);
 285         unsigned int i;
 286
 287         for (i = 0; i != end; i++)
 288                 dst[i] = src[i];
 289 }
 290
 291 static inline void
 292 bitmap_or(unsigned long *dst, const unsigned long *src1,
 293     const unsigned long *src2, const unsigned int size)
 294 {
 295         const unsigned int end = BITS_TO_LONGS(size);
 296         unsigned int i;
 297
 298         for (i = 0; i != end; i++)
 299                 dst[i] = src1[i] | src2[i];
 300 }
 301
 302 static inline void
 303 bitmap_and(unsigned long *dst, const unsigned long *src1,
 304     const unsigned long *src2, const unsigned int size)
 305 {
 306         const unsigned int end = BITS_TO_LONGS(size);
 307         unsigned int i;
 308
 309         for (i = 0; i != end; i++)
 310                 dst[i] = src1[i] & src2[i];
 311 }
 312
 313 static inline void
 314 bitmap_andnot(unsigned long *dst, const unsigned long *src1,
 315     const unsigned long *src2, const unsigned int size)
 316 {
 317         const unsigned int end = BITS_TO_LONGS(size);
 318         unsigned int i;
 319
 320         for (i = 0; i != end; i++)
 321                 dst[i] = src1[i] & ~src2[i];
 322 }
 323
 324 static inline void
 325 bitmap_xor(unsigned long *dst, const unsigned long *src1,
 326     const unsigned long *src2, const unsigned int size)
 327 {
 328         const unsigned int end = BITS_TO_LONGS(size);
 329         unsigned int i;
 330
 331         for (i = 0; i != end; i++)
 332                 dst[i] = src1[i] ^ src2[i];
 333 }
 334
 335 static inline unsigned long *
 336 bitmap_alloc(unsigned int size, gfp_t flags)
 337 {
 338         return (kmalloc_array(BITS_TO_LONGS(size),
 339             sizeof(unsigned long), flags));
 340 }
 341
 342 static inline unsigned long *
 343 bitmap_zalloc(unsigned int size, gfp_t flags)
 344 {
 345         return (bitmap_alloc(size, flags | __GFP_ZERO));
 346 }
 347
 348 static inline void
 349 bitmap_free(const unsigned long *bitmap)
 350 {
 351         kfree(bitmap);
 352 }
 353
 354 #endif                                  /* _LINUXKPI_LINUX_BITMAP_H_ */