1 #ifndef __XEN_BITMAP_H
2 #define __XEN_BITMAP_H
3
4 #ifndef __ASSEMBLY__
5
6 #include <xen/lib.h>
7 #include <xen/types.h>
8 #include <xen/bitops.h>
9
10 /*
11 * bitmaps provide bit arrays that consume one or more unsigned
12 * longs. The bitmap interface and available operations are listed
13 * here, in bitmap.h
14 *
15 * Function implementations generic to all architectures are in
16 * lib/bitmap.c. Functions implementations that are architecture
17 * specific are in various asm/bitops.h headers
18 * and other arch/<arch> specific files.
19 *
20 * See lib/bitmap.c for more details.
21 */
22
23 /*
24 * The available bitmap operations and their rough meaning in the
25 * case that the bitmap is a single unsigned long are thus:
26 *
27 * bitmap_zero(dst, nbits) *dst = 0UL
28 * bitmap_fill(dst, nbits) *dst = ~0UL
29 * bitmap_copy(dst, src, nbits) *dst = *src
30 * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2
31 * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2
32 * bitmap_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2
33 * bitmap_andnot(dst, src1, src2, nbits) *dst = *src1 & ~(*src2)
34 * bitmap_complement(dst, src, nbits) *dst = ~(*src)
35 * bitmap_equal(src1, src2, nbits) Are *src1 and *src2 equal?
36 * bitmap_intersects(src1, src2, nbits) Do *src1 and *src2 overlap?
37 * bitmap_subset(src1, src2, nbits) Is *src1 a subset of *src2?
38 * bitmap_empty(src, nbits) Are all bits zero in *src?
39 * bitmap_full(src, nbits) Are all bits set in *src?
40 * bitmap_weight(src, nbits) Hamming Weight: number set bits
41 */
42
43 /*
44 * Also the following operations in asm/bitops.h apply to bitmaps.
45 *
46 * set_bit(bit, addr) *addr |= bit
47 * clear_bit(bit, addr) *addr &= ~bit
48 * change_bit(bit, addr) *addr ^= bit
49 * test_bit(bit, addr) Is bit set in *addr?
50 * test_and_set_bit(bit, addr) Set bit and return old value
51 * test_and_clear_bit(bit, addr) Clear bit and return old value
52 * test_and_change_bit(bit, addr) Change bit and return old value
53 * find_first_zero_bit(addr, nbits) Position first zero bit in *addr
54 * find_first_bit(addr, nbits) Position first set bit in *addr
55 * find_next_zero_bit(addr, nbits, bit) Position next zero bit in *addr >= bit
56 * find_next_bit(addr, nbits, bit) Position next set bit in *addr >= bit
57 */
58
59 /*
60 * The DECLARE_BITMAP(name,bits) macro, in xen/types.h, can be used
61 * to declare an array named 'name' of just enough unsigned longs to
62 * contain all bit positions from 0 to 'bits' - 1.
63 */
64
65 /*
66 * lib/bitmap.c provides these functions:
67 */
68
69 int __bitmap_empty(const unsigned long *bitmap, unsigned int bits);
70 int __bitmap_full(const unsigned long *bitmap, unsigned int bits);
71 int __bitmap_equal(const unsigned long *bitmap1,
72 const unsigned long *bitmap2, unsigned int bits);
73 void __bitmap_complement(unsigned long *dst, const unsigned long *src,
74 unsigned int bits);
75 void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
76 const unsigned long *bitmap2, unsigned int bits);
77 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
78 const unsigned long *bitmap2, unsigned int bits);
79 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
80 const unsigned long *bitmap2, unsigned int bits);
81 void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
82 const unsigned long *bitmap2, unsigned int bits);
83 int __bitmap_intersects(const unsigned long *bitmap1,
84 const unsigned long *bitmap2, unsigned int bits);
85 int __bitmap_subset(const unsigned long *bitmap1,
86 const unsigned long *bitmap2, unsigned int bits);
87 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits);
88 extern void __bitmap_set(unsigned long *map, unsigned int start, int len);
89 extern void __bitmap_clear(unsigned long *map, unsigned int start, int len);
90
91 extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
92 extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
93 extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
94
95 #define BITMAP_LAST_WORD_MASK(nbits) \
96 ( \
97 ((nbits) % BITS_PER_LONG) ? \
98 (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
99 )
100
101 #define bitmap_bytes(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))
102
103 #define bitmap_switch(nbits, zero, small, large) \
104 unsigned int n__ = (nbits); \
105 if (__builtin_constant_p(nbits) && !n__) { \
106 zero; \
107 } else if (__builtin_constant_p(nbits) && n__ <= BITS_PER_LONG) { \
108 small; \
109 } else { \
110 large; \
111 }
112
bitmap_zero(unsigned long * dst,unsigned int nbits)113 static inline void bitmap_zero(unsigned long *dst, unsigned int nbits)
114 {
115 bitmap_switch(nbits,,
116 *dst = 0UL,
117 memset(dst, 0, bitmap_bytes(nbits)));
118 }
119
bitmap_fill(unsigned long * dst,unsigned int nbits)120 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
121 {
122 size_t nlongs = BITS_TO_LONGS(nbits);
123
124 switch (nlongs) {
125 case 0:
126 break;
127 default:
128 memset(dst, -1, (nlongs - 1) * sizeof(unsigned long));
129 /* fall through */
130 case 1:
131 dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
132 break;
133 }
134 }
135
bitmap_copy(unsigned long * dst,const unsigned long * src,unsigned int nbits)136 static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
137 unsigned int nbits)
138 {
139 bitmap_switch(nbits,,
140 *dst = *src,
141 memcpy(dst, src, bitmap_bytes(nbits)));
142 }
143
bitmap_and(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,unsigned int nbits)144 static inline void bitmap_and(unsigned long *dst, const unsigned long *src1,
145 const unsigned long *src2, unsigned int nbits)
146 {
147 bitmap_switch(nbits,,
148 *dst = *src1 & *src2,
149 __bitmap_and(dst, src1, src2, nbits));
150 }
151
bitmap_or(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,unsigned int nbits)152 static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
153 const unsigned long *src2, unsigned int nbits)
154 {
155 bitmap_switch(nbits,,
156 *dst = *src1 | *src2,
157 __bitmap_or(dst, src1, src2, nbits));
158 }
159
bitmap_xor(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,unsigned int nbits)160 static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
161 const unsigned long *src2, unsigned int nbits)
162 {
163 bitmap_switch(nbits,,
164 *dst = *src1 ^ *src2,
165 __bitmap_xor(dst, src1, src2, nbits));
166 }
167
bitmap_andnot(unsigned long * dst,const unsigned long * src1,const unsigned long * src2,unsigned int nbits)168 static inline void bitmap_andnot(unsigned long *dst, const unsigned long *src1,
169 const unsigned long *src2, unsigned int nbits)
170 {
171 bitmap_switch(nbits,,
172 *dst = *src1 & ~*src2,
173 __bitmap_andnot(dst, src1, src2, nbits));
174 }
175
bitmap_complement(unsigned long * dst,const unsigned long * src,unsigned int nbits)176 static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
177 unsigned int nbits)
178 {
179 bitmap_switch(nbits,,
180 *dst = ~*src & BITMAP_LAST_WORD_MASK(nbits),
181 __bitmap_complement(dst, src, nbits));
182 }
183
bitmap_equal(const unsigned long * src1,const unsigned long * src2,unsigned int nbits)184 static inline int bitmap_equal(const unsigned long *src1,
185 const unsigned long *src2, unsigned int nbits)
186 {
187 bitmap_switch(nbits,
188 return -1,
189 return !((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits)),
190 return __bitmap_equal(src1, src2, nbits));
191 }
192
bitmap_intersects(const unsigned long * src1,const unsigned long * src2,unsigned int nbits)193 static inline int bitmap_intersects(const unsigned long *src1,
194 const unsigned long *src2, unsigned int nbits)
195 {
196 bitmap_switch(nbits,
197 return -1,
198 return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0,
199 return __bitmap_intersects(src1, src2, nbits));
200 }
201
bitmap_subset(const unsigned long * src1,const unsigned long * src2,unsigned int nbits)202 static inline int bitmap_subset(const unsigned long *src1,
203 const unsigned long *src2, unsigned int nbits)
204 {
205 bitmap_switch(nbits,
206 return -1,
207 return !((*src1 & ~*src2) & BITMAP_LAST_WORD_MASK(nbits)),
208 return __bitmap_subset(src1, src2, nbits));
209 }
210
bitmap_empty(const unsigned long * src,unsigned int nbits)211 static inline int bitmap_empty(const unsigned long *src, unsigned int nbits)
212 {
213 bitmap_switch(nbits,
214 return -1,
215 return !(*src & BITMAP_LAST_WORD_MASK(nbits)),
216 return __bitmap_empty(src, nbits));
217 }
218
bitmap_full(const unsigned long * src,unsigned int nbits)219 static inline int bitmap_full(const unsigned long *src, unsigned int nbits)
220 {
221 bitmap_switch(nbits,
222 return -1,
223 return !(~*src & BITMAP_LAST_WORD_MASK(nbits)),
224 return __bitmap_full(src, nbits));
225 }
226
bitmap_weight(const unsigned long * src,unsigned int nbits)227 static inline unsigned int bitmap_weight(const unsigned long *src,
228 unsigned int nbits)
229 {
230 return __bitmap_weight(src, nbits);
231 }
232
233 #include <xen/byteorder.h>
234
235 #ifdef __LITTLE_ENDIAN
236 #define BITMAP_MEM_ALIGNMENT 8
237 #else
238 #define BITMAP_MEM_ALIGNMENT (8 * sizeof(unsigned long))
239 #endif
240 #define BITMAP_MEM_MASK (BITMAP_MEM_ALIGNMENT - 1)
241 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
242
bitmap_set(unsigned long * map,unsigned int start,unsigned int nbits)243 static inline void bitmap_set(unsigned long *map, unsigned int start,
244 unsigned int nbits)
245 {
246 if (__builtin_constant_p(nbits) && nbits == 1)
247 __set_bit(start, map);
248 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
249 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
250 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
251 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
252 memset((char *)map + start / 8, 0xff, nbits / 8);
253 else
254 __bitmap_set(map, start, nbits);
255 }
256
bitmap_clear(unsigned long * map,unsigned int start,unsigned int nbits)257 static inline void bitmap_clear(unsigned long *map, unsigned int start,
258 unsigned int nbits)
259 {
260 if (__builtin_constant_p(nbits) && nbits == 1)
261 __clear_bit(start, map);
262 else if (__builtin_constant_p(start & BITMAP_MEM_MASK) &&
263 IS_ALIGNED(start, BITMAP_MEM_ALIGNMENT) &&
264 __builtin_constant_p(nbits & BITMAP_MEM_MASK) &&
265 IS_ALIGNED(nbits, BITMAP_MEM_ALIGNMENT))
266 memset((char *)map + start / 8, 0, nbits / 8);
267 else
268 __bitmap_clear(map, start, nbits);
269 }
270
271 #undef bitmap_switch
272 #undef bitmap_bytes
273
274 /**
275 * bitmap_for_each - bitate over every set bit in a memory region
276 * @bit: The integer bitator
277 * @addr: The address to base the search on
278 * @size: The maximum size to search
279 */
280 #define bitmap_for_each(bit, addr, size) \
281 for ( (bit) = find_first_bit(addr, size); \
282 (bit) < (size); \
283 (bit) = find_next_bit(addr, size, (bit) + 1) )
284
285
286 struct xenctl_bitmap;
287 int xenctl_bitmap_to_bitmap(unsigned long *bitmap,
288 const struct xenctl_bitmap *xenctl_bitmap,
289 unsigned int nbits);
290 int bitmap_to_xenctl_bitmap(struct xenctl_bitmap *xenctl_bitmap,
291 const unsigned long *bitmap, unsigned int nbits);
292
293 #endif /* __ASSEMBLY__ */
294
295 #endif /* __XEN_BITMAP_H */
296