include/linux/bitmap.h

   1 // SPDX-License-Identifier: GPL-2.0+
   2 #ifndef __LINUX_BITMAP_H
   3 #define __LINUX_BITMAP_H
   4
   5 #include <asm/types.h>
   6 #include <linux/types.h>
   7 #include <linux/bitops.h>
   8 #include <linux/string.h>
   9
  10 #ifdef __LITTLE_ENDIAN
  11 #define BITMAP_MEM_ALIGNMENT 8
  12 #else
  13 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
  14 #endif
  15 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
  16
  17 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
  18 #define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
  19 #define small_const_nbits(nbits) \
  20         (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
  21
  22 static inline void
  23 __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
  24             const unsigned long *bitmap2, unsigned int bits)
  25 {
  26         unsigned int k;
  27         unsigned int nr = BITS_TO_LONGS(bits);
  28
  29         for (k = 0; k < nr; k++)
  30                 dst[k] = bitmap1[k] | bitmap2[k];
  31 }
  32
  33 static inline int
  34 __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
  35 {
  36         unsigned int k, lim = bits / BITS_PER_LONG;
  37         int w = 0;
  38
  39         for (k = 0; k < lim; k++)
  40                 w += hweight_long(bitmap[k]);
  41
  42         if (bits % BITS_PER_LONG)
  43                 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
  44
  45         return w;
  46 }
  47
  48 static inline void
  49 __bitmap_set(unsigned long *map, unsigned int start, int len)
  50 {
  51         unsigned long *p = map + BIT_WORD(start);
  52         const unsigned int size = start + len;
  53         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  54         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
  55
  56         while (len - bits_to_set >= 0) {
  57                 *p |= mask_to_set;
  58                 len -= bits_to_set;
  59                 bits_to_set = BITS_PER_LONG;
  60                 mask_to_set = ~0UL;
  61                 p++;
  62         }
  63         if (len) {
  64                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
  65                 *p |= mask_to_set;
  66         }
  67 }
  68
  69 static inline void
  70 __bitmap_clear(unsigned long *map, unsigned int start, int len)
  71 {
  72         unsigned long *p = map + BIT_WORD(start);
  73         const unsigned int size = start + len;
  74         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
  75         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
  76
  77         while (len - bits_to_clear >= 0) {
  78                 *p &= ~mask_to_clear;
  79                 len -= bits_to_clear;
  80                 bits_to_clear = BITS_PER_LONG;
  81                 mask_to_clear = ~0UL;
  82                 p++;
  83         }
  84         if (len) {
  85                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
  86                 *p &= ~mask_to_clear;
  87         }
  88 }
  89
  90 static inline void bitmap_zero(unsigned long *dst, int nbits)
  91 {
  92         if (small_const_nbits(nbits)) {
  93                 *dst = 0UL;
  94         } else {
  95                 int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
  96
  97                 memset(dst, 0, len);
  98         }
  99 }
 100
 101 static inline unsigned long
 102 find_next_bit(const unsigned long *addr, unsigned long size,
 103               unsigned long offset)
 104 {
 105         const unsigned long *p = addr + BIT_WORD(offset);
 106         unsigned long result = offset & ~(BITS_PER_LONG - 1);
 107         unsigned long tmp;
 108
 109         if (offset >= size)
 110                 return size;
 111         size -= result;
 112         offset %= BITS_PER_LONG;
 113         if (offset) {
 114                 tmp = *(p++);
 115                 tmp &= (~0UL << offset);
 116                 if (size < BITS_PER_LONG)
 117                         goto found_first;
 118                 if (tmp)
 119                         goto found_middle;
 120                 size -= BITS_PER_LONG;
 121                 result += BITS_PER_LONG;
 122         }
 123         while (size & ~(BITS_PER_LONG - 1)) {
 124                 tmp = *(p++);
 125                 if ((tmp))
 126                         goto found_middle;
 127                 result += BITS_PER_LONG;
 128                 size -= BITS_PER_LONG;
 129         }
 130         if (!size)
 131                 return result;
 132         tmp = *p;
 133
 134 found_first:
 135         tmp &= (~0UL >> (BITS_PER_LONG - size));
 136         if (tmp == 0UL)         /* Are any bits set? */
 137                 return result + size;   /* Nope. */
 138 found_middle:
 139         return result + __ffs(tmp);
 140 }
 141
 142 /*
 143  * Find the first set bit in a memory region.
 144  */
 145 static inline unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 146 {
 147         unsigned long idx;
 148
 149         for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 150                 if (addr[idx])
 151                         return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
 152         }
 153
 154         return size;
 155 }
 156
 157 #define for_each_set_bit(bit, addr, size) \
 158         for ((bit) = find_first_bit((addr), (size));            \
 159              (bit) < (size);                                    \
 160              (bit) = find_next_bit((addr), (size), (bit) + 1))
 161
 162 static inline unsigned long
 163 bitmap_find_next_zero_area(unsigned long *map,
 164                            unsigned long size,
 165                            unsigned long start,
 166                            unsigned int nr, unsigned long align_mask)
 167 {
 168         unsigned long index, end, i;
 169 again:
 170         index = find_next_zero_bit(map, size, start);
 171
 172         /*
 173          * Align allocation
 174          */
 175         index = (index + align_mask) & ~align_mask;
 176
 177         end = index + nr;
 178         if (end > size)
 179                 return end;
 180         i = find_next_bit(map, end, index);
 181         if (i < end) {
 182                 start = i + 1;
 183                 goto again;
 184         }
 185         return index;
 186 }
 187
 188 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
 189 {
 190         if (small_const_nbits(nbits)) {
 191                 *dst = ~0UL;
 192         } else {
 193                 unsigned int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
 194
 195                 memset(dst, 0xff, len);
 196         }
 197 }
 198
 199 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
 200                              const unsigned long *src2, unsigned int nbits)
 201 {
 202         if (small_const_nbits(nbits))
 203                 *dst = *src1 | *src2;
 204         else
 205                 __bitmap_or(dst, src1, src2, nbits);
 206 }
 207
 208 static inline int bitmap_weight(const unsigned long *src, unsigned int nbits)
 209 {
 210         if (small_const_nbits(nbits))
 211                 return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
 212         return __bitmap_weight(src, nbits);
 213 }
 214
 215 static inline void bitmap_set(unsigned long *map, unsigned int start,
 216                               unsigned int nbits)
 217 {
 218         if (__builtin_constant_p(nbits) && nbits == 1)
 219                 __set_bit(start, map);
 220         else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
 221                  IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
 222                  __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
 223                  IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
 224                 memset((char *)map + start / 8, 0xff, nbits / 8);
 225         else
 226                 __bitmap_set(map, start, nbits);
 227 }
 228
 229 static inline void bitmap_clear(unsigned long *map, unsigned int start,
 230                                 unsigned int nbits)
 231 {
 232         if (__builtin_constant_p(nbits) && nbits == 1)
 233                 __clear_bit(start, map);
 234         else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
 235                  IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
 236                  __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
 237                  IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
 238                 memset((char *)map + start / 8, 0, nbits / 8);
 239         else
 240                 __bitmap_clear(map, start, nbits);
 241 }
 242
 243 #endif /* __LINUX_BITMAP_H */