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 22static 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 33static 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 48static 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 69static 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 90static 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 101static inline unsigned long 102find_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 134found_first: 135 tmp &= (~0UL >> (BITS_PER_LONG - size)); 136 if (tmp == 0UL) /* Are any bits set? */ 137 return result + size; /* Nope. */ 138found_middle: 139 return result + __ffs(tmp); 140} 141 142/* 143 * Find the first set bit in a memory region. 144 */ 145static 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 162static inline unsigned long 163bitmap_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; 169again: 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 188static 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 199static 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 208static 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 215static 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 229static 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 */ 244