virbitmap: Refactor virBitmapParse to avoid access beyond bounds of array
[libvirt.git] / src / util / virbitmap.c
1 /*
2  * virbitmap.h: Simple bitmap operations
3  *
4  * Copyright (C) 2010-2013 Red Hat, Inc.
5  * Copyright (C) 2010 Novell, Inc.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this library.  If not, see
19  * <http://www.gnu.org/licenses/>.
20  *
21  * Author: Jim Fehlig <jfehlig@novell.com>
22  */
23
24 #include <config.h>
25
26 #include <limits.h>
27 #include <stdint.h>
28 #include <stdio.h>
29 #include <string.h>
30 #include <stdlib.h>
31 #include <sys/types.h>
32
33 #include "virbitmap.h"
34 #include "viralloc.h"
35 #include "virbuffer.h"
36 #include "c-ctype.h"
37 #include "count-one-bits.h"
38 #include "virstring.h"
39 #include "virerror.h"
40
41 #define VIR_FROM_THIS VIR_FROM_NONE
42
43 struct _virBitmap {
44     size_t max_bit;
45     size_t map_len;
46     unsigned long *map;
47 };
48
49
50 #define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned long) * CHAR_BIT)
51 #define VIR_BITMAP_UNIT_OFFSET(b) ((b) / VIR_BITMAP_BITS_PER_UNIT)
52 #define VIR_BITMAP_BIT_OFFSET(b)  ((b) % VIR_BITMAP_BITS_PER_UNIT)
53 #define VIR_BITMAP_BIT(b)         (1UL << VIR_BITMAP_BIT_OFFSET(b))
54
55
56 /**
57  * virBitmapNew:
58  * @size: number of bits
59  *
60  * Allocate a bitmap capable of containing @size bits.
61  *
62  * Returns a pointer to the allocated bitmap or NULL if
63  * memory cannot be allocated.
64  */
65 virBitmapPtr virBitmapNew(size_t size)
66 {
67     virBitmapPtr bitmap;
68     size_t sz;
69
70     if (SIZE_MAX - VIR_BITMAP_BITS_PER_UNIT < size || size == 0) {
71         virReportOOMError();
72         return NULL;
73     }
74
75     sz = (size + VIR_BITMAP_BITS_PER_UNIT - 1) /
76           VIR_BITMAP_BITS_PER_UNIT;
77
78     if (VIR_ALLOC(bitmap) < 0)
79         return NULL;
80
81     if (VIR_ALLOC_N(bitmap->map, sz) < 0) {
82         VIR_FREE(bitmap);
83         return NULL;
84     }
85
86     bitmap->max_bit = size;
87     bitmap->map_len = sz;
88     return bitmap;
89 }
90
91 /**
92  * virBitmapFree:
93  * @bitmap: previously allocated bitmap
94  *
95  * Free @bitmap previously allocated by virBitmapNew.
96  */
97 void virBitmapFree(virBitmapPtr bitmap)
98 {
99     if (bitmap) {
100         VIR_FREE(bitmap->map);
101         VIR_FREE(bitmap);
102     }
103 }
104
105
106 int virBitmapCopy(virBitmapPtr dst, virBitmapPtr src)
107 {
108     if (dst->max_bit != src->max_bit) {
109         errno = EINVAL;
110         return -1;
111     }
112
113     memcpy(dst->map, src->map, src->map_len * sizeof(src->map[0]));
114
115     return 0;
116 }
117
118
119 /**
120  * virBitmapSetBit:
121  * @bitmap: Pointer to bitmap
122  * @b: bit position to set
123  *
124  * Set bit position @b in @bitmap
125  *
126  * Returns 0 on if bit is successfully set, -1 on error.
127  */
128 int virBitmapSetBit(virBitmapPtr bitmap, size_t b)
129 {
130     if (bitmap->max_bit <= b)
131         return -1;
132
133     bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] |= VIR_BITMAP_BIT(b);
134     return 0;
135 }
136
137 /**
138  * virBitmapClearBit:
139  * @bitmap: Pointer to bitmap
140  * @b: bit position to clear
141  *
142  * Clear bit position @b in @bitmap
143  *
144  * Returns 0 on if bit is successfully clear, -1 on error.
145  */
146 int virBitmapClearBit(virBitmapPtr bitmap, size_t b)
147 {
148     if (bitmap->max_bit <= b)
149         return -1;
150
151     bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] &= ~VIR_BITMAP_BIT(b);
152     return 0;
153 }
154
155 /* Helper function. caller must ensure b < bitmap->max_bit */
156 static bool virBitmapIsSet(virBitmapPtr bitmap, size_t b)
157 {
158     return !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
159 }
160
161 /**
162  * virBitmapGetBit:
163  * @bitmap: Pointer to bitmap
164  * @b: bit position to get
165  * @result: bool pointer to receive bit setting
166  *
167  * Get setting of bit position @b in @bitmap and store in @result
168  *
169  * On success, @result will contain the setting of @b and 0 is
170  * returned.  On failure, -1 is returned and @result is unchanged.
171  */
172 int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result)
173 {
174     if (bitmap->max_bit <= b)
175         return -1;
176
177     *result = virBitmapIsSet(bitmap, b);
178     return 0;
179 }
180
181 /**
182  * virBitmapString:
183  * @bitmap: Pointer to bitmap
184  *
185  * Convert @bitmap to printable string.
186  *
187  * Returns pointer to the string or NULL on error.
188  */
189 char *virBitmapString(virBitmapPtr bitmap)
190 {
191     virBuffer buf = VIR_BUFFER_INITIALIZER;
192     size_t sz;
193
194     virBufferAddLit(&buf, "0x");
195
196     sz = bitmap->map_len;
197
198     while (sz--) {
199         virBufferAsprintf(&buf, "%0*lx",
200                           VIR_BITMAP_BITS_PER_UNIT / 4,
201                           bitmap->map[sz]);
202     }
203
204     if (virBufferError(&buf)) {
205         virBufferFreeAndReset(&buf);
206         return NULL;
207     }
208
209     return virBufferContentAndReset(&buf);
210 }
211
212 /**
213  * virBitmapFormat:
214  * @bitmap: the bitmap
215  *
216  * This function is the counterpart of virBitmapParse. This function creates
217  * a human-readable string representing the bits in bitmap.
218  *
219  * See virBitmapParse for the format of @str.
220  *
221  * Returns the string on success or NULL otherwise. Caller should call
222  * VIR_FREE to free the string.
223  */
224 char *virBitmapFormat(virBitmapPtr bitmap)
225 {
226     virBuffer buf = VIR_BUFFER_INITIALIZER;
227     bool first = true;
228     int start, cur, prev;
229
230     if (!bitmap)
231         return NULL;
232
233     cur = virBitmapNextSetBit(bitmap, -1);
234     if (cur < 0) {
235         char *ret;
236         ignore_value(VIR_STRDUP(ret, ""));
237         return ret;
238     }
239
240     start = prev = cur;
241     while (prev >= 0) {
242         cur = virBitmapNextSetBit(bitmap, prev);
243
244         if (cur == prev + 1) {
245             prev = cur;
246             continue;
247         }
248
249         /* cur < 0 or cur > prev + 1 */
250
251         if (!first)
252             virBufferAddLit(&buf, ",");
253         else
254             first = false;
255
256         if (prev == start)
257             virBufferAsprintf(&buf, "%d", start);
258         else
259             virBufferAsprintf(&buf, "%d-%d", start, prev);
260
261         start = prev = cur;
262     }
263
264     if (virBufferError(&buf)) {
265         virBufferFreeAndReset(&buf);
266         return NULL;
267     }
268
269     return virBufferContentAndReset(&buf);
270 }
271
272 /**
273  * virBitmapParse:
274  * @str: points to a string representing a human-readable bitmap
275  * @terminator: character separating the bitmap to parse
276  * @bitmap: a bitmap created from @str
277  * @bitmapSize: the upper limit of num of bits in created bitmap
278  *
279  * This function is the counterpart of virBitmapFormat. This function creates
280  * a bitmap, in which bits are set according to the content of @str.
281  *
282  * @str is a comma separated string of fields N, which means a number of bit
283  * to set, and ^N, which means to unset the bit, and N-M for ranges of bits
284  * to set.
285  *
286  * To allow parsing of bitmaps within larger strings it is possible to set
287  * a termination character in the argument @terminator. When the character
288  * in @terminator is encountered in @str, the parsing of the bitmap stops.
289  * Pass 0 as @terminator if it is not needed. Whitespace characters may not
290  * be used as terminators.
291  *
292  * Returns the number of bits set in @bitmap, or -1 in case of error.
293  */
294 int
295 virBitmapParse(const char *str,
296                char terminator,
297                virBitmapPtr *bitmap,
298                size_t bitmapSize)
299 {
300     bool neg = false;
301     const char *cur;
302     char *tmp;
303     size_t i;
304     int start, last;
305
306     if (!str)
307         return -1;
308
309     cur = str;
310     virSkipSpaces(&cur);
311
312     if (*cur == 0)
313         return -1;
314
315     *bitmap = virBitmapNew(bitmapSize);
316     if (!*bitmap)
317         return -1;
318
319     while (*cur != 0 && *cur != terminator) {
320         /*
321          * 3 constructs are allowed:
322          *     - N   : a single CPU number
323          *     - N-M : a range of CPU numbers with N < M
324          *     - ^N  : remove a single CPU number from the current set
325          */
326         if (*cur == '^') {
327             cur++;
328             neg = true;
329         }
330
331         if (!c_isdigit(*cur))
332             goto error;
333
334         if (virStrToLong_i(cur, &tmp, 10, &start) < 0)
335             goto error;
336         if (start < 0)
337             goto error;
338
339         cur = tmp;
340
341         virSkipSpaces(&cur);
342
343         if (*cur == ',' || *cur == 0 || *cur == terminator) {
344             if (neg) {
345                 if (virBitmapClearBit(*bitmap, start) < 0)
346                     goto error;
347             } else {
348                 if (virBitmapSetBit(*bitmap, start) < 0)
349                     goto error;
350             }
351         } else if (*cur == '-') {
352             if (neg)
353                 goto error;
354
355             cur++;
356             virSkipSpaces(&cur);
357
358             if (virStrToLong_i(cur, &tmp, 10, &last) < 0)
359                 goto error;
360             if (last < start)
361                 goto error;
362
363             cur = tmp;
364
365             for (i = start; i <= last; i++) {
366                 if (virBitmapSetBit(*bitmap, i) < 0)
367                     goto error;
368             }
369
370             virSkipSpaces(&cur);
371         }
372
373         if (*cur == ',') {
374             cur++;
375             virSkipSpaces(&cur);
376             neg = false;
377         } else if (*cur == 0 || *cur == terminator) {
378             break;
379         } else {
380             goto error;
381         }
382     }
383
384     return virBitmapCountBits(*bitmap);
385
386 error:
387     virBitmapFree(*bitmap);
388     *bitmap = NULL;
389     return -1;
390 }
391
392 /**
393  * virBitmapNewCopy:
394  * @src: the source bitmap.
395  *
396  * Makes a copy of bitmap @src.
397  *
398  * returns the copied bitmap on success, or NULL otherwise. Caller
399  * should call virBitmapFree to free the returned bitmap.
400  */
401 virBitmapPtr virBitmapNewCopy(virBitmapPtr src)
402 {
403     virBitmapPtr dst;
404
405     if ((dst = virBitmapNew(src->max_bit)) == NULL)
406         return NULL;
407
408     if (virBitmapCopy(dst, src) != 0) {
409         virBitmapFree(dst);
410         return NULL;
411     }
412
413     return dst;
414 }
415
416 /**
417  * virBitmapNewData:
418  * @data: the data
419  * @len: length of @data in bytes
420  *
421  * Allocate a bitmap from a chunk of data containing bits
422  * information
423  *
424  * Returns a pointer to the allocated bitmap or NULL if
425  * memory cannot be allocated.
426  */
427 virBitmapPtr virBitmapNewData(void *data, int len)
428 {
429     virBitmapPtr bitmap;
430     size_t i, j;
431     unsigned long *p;
432     unsigned char *bytes = data;
433
434     bitmap = virBitmapNew(len * CHAR_BIT);
435     if (!bitmap)
436         return NULL;
437
438     /* le64toh is not provided by gnulib, so we do the conversion by hand */
439     p = bitmap->map;
440     for (i = j = 0; i < len; i++, j++) {
441         if (j == sizeof(*p)) {
442             j = 0;
443             p++;
444         }
445         *p |= (unsigned long) bytes[i] << (j * CHAR_BIT);
446     }
447
448     return bitmap;
449 }
450
451 /**
452  * virBitmapToData:
453  * @data: the data
454  * @len: len of @data in byte
455  *
456  * Convert a bitmap to a chunk of data containing bits information.
457  * Data consists of sequential bytes, with lower bytes containing
458  * lower bits.
459  *
460  * Returns 0 on success, -1 otherwise.
461  */
462 int virBitmapToData(virBitmapPtr bitmap, unsigned char **data, int *dataLen)
463 {
464     int len;
465     unsigned long *l;
466     size_t i, j;
467     unsigned char *bytes;
468
469     len = (bitmap->max_bit + CHAR_BIT - 1) / CHAR_BIT;
470
471     if (VIR_ALLOC_N(*data, len) < 0)
472         return -1;
473
474     bytes = *data;
475     *dataLen = len;
476
477     /* htole64 is not provided by gnulib, so we do the conversion by hand */
478     l = bitmap->map;
479     for (i = j = 0; i < len; i++, j++) {
480         if (j == sizeof(*l)) {
481             j = 0;
482             l++;
483         }
484         bytes[i] = *l >> (j * CHAR_BIT);
485     }
486
487     return 0;
488 }
489
490 /**
491  * virBitmapEqual:
492  * @b1: bitmap 1
493  * @b2: bitmap 2
494  *
495  * Compares two bitmaps, whose lengths can be different from each other.
496  *
497  * Returns true if two bitmaps have exactly the same set of bits set,
498  * otherwise false.
499  */
500 bool virBitmapEqual(virBitmapPtr b1, virBitmapPtr b2)
501 {
502     virBitmapPtr tmp;
503     size_t i;
504
505     if (b1->max_bit > b2->max_bit) {
506         tmp = b1;
507         b1 = b2;
508         b2 = tmp;
509     }
510
511     /* Now b1 is the smaller one, if not equal */
512
513     for (i = 0; i < b1->map_len; i++) {
514         if (b1->map[i] != b2->map[i])
515             return false;
516     }
517
518     for (; i < b2->map_len; i++) {
519         if (b2->map[i])
520             return false;
521     }
522
523     return true;
524 }
525
526 size_t virBitmapSize(virBitmapPtr bitmap)
527 {
528     return bitmap->max_bit;
529 }
530
531 /**
532  * virBitmapSetAll:
533  * @bitmap: the bitmap
534  *
535  * set all bits in @bitmap.
536  */
537 void virBitmapSetAll(virBitmapPtr bitmap)
538 {
539     int tail = bitmap->max_bit % VIR_BITMAP_BITS_PER_UNIT;
540
541     memset(bitmap->map, 0xff,
542            bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT));
543
544     /* Ensure tail bits are clear.  */
545     if (tail)
546         bitmap->map[bitmap->map_len - 1] &=
547             -1UL >> (VIR_BITMAP_BITS_PER_UNIT - tail);
548 }
549
550 /**
551  * virBitmapClearAll:
552  * @bitmap: the bitmap
553  *
554  * clear all bits in @bitmap.
555  */
556 void virBitmapClearAll(virBitmapPtr bitmap)
557 {
558     memset(bitmap->map, 0,
559            bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT));
560 }
561
562 /**
563  * virBitmapIsAllSet:
564  * @bitmap: the bitmap to check
565  *
566  * check if all bits in @bitmap are set.
567  */
568 bool virBitmapIsAllSet(virBitmapPtr bitmap)
569 {
570     size_t i;
571     int unusedBits;
572     size_t sz;
573
574     unusedBits = bitmap->map_len * VIR_BITMAP_BITS_PER_UNIT - bitmap->max_bit;
575
576     sz = bitmap->map_len;
577     if (unusedBits > 0)
578         sz--;
579
580     for (i = 0; i < sz; i++)
581         if (bitmap->map[i] != -1)
582             return false;
583
584     if (unusedBits > 0) {
585         if ((bitmap->map[sz] & ((1UL << (VIR_BITMAP_BITS_PER_UNIT - unusedBits)) - 1))
586             != ((1UL << (VIR_BITMAP_BITS_PER_UNIT - unusedBits)) - 1))
587             return false;
588     }
589
590     return true;
591 }
592
593 /**
594  * virBitmapIsAllClear:
595  * @bitmap: the bitmap to check
596  *
597  * check if all bits in @bitmap are clear
598  */
599 bool virBitmapIsAllClear(virBitmapPtr bitmap)
600 {
601     size_t i;
602
603     for (i = 0; i < bitmap->map_len; i++)
604         if (bitmap->map[i] != 0)
605             return false;
606
607     return true;
608 }
609
610 /**
611  * virBitmapNextSetBit:
612  * @bitmap: the bitmap
613  * @pos: the position after which to search for a set bit
614  *
615  * Search for the first set bit after position @pos in bitmap @bitmap.
616  * @pos can be -1 to search for the first set bit. Position starts
617  * at 0.
618  *
619  * Returns the position of the found bit, or -1 if no bit found.
620  */
621 ssize_t
622 virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
623 {
624     size_t nl;
625     size_t nb;
626     unsigned long bits;
627
628     if (pos < 0)
629         pos = -1;
630
631     pos++;
632
633     if (pos >= bitmap->max_bit)
634         return -1;
635
636     nl = pos / VIR_BITMAP_BITS_PER_UNIT;
637     nb = pos % VIR_BITMAP_BITS_PER_UNIT;
638
639     bits = bitmap->map[nl] & ~((1UL << nb) - 1);
640
641     while (bits == 0 && ++nl < bitmap->map_len) {
642         bits = bitmap->map[nl];
643     }
644
645     if (bits == 0)
646         return -1;
647
648     return ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
649 }
650
651 /**
652  * virBitmapNextClearBit:
653  * @bitmap: the bitmap
654  * @pos: the position after which to search for a clear bit
655  *
656  * Search for the first clear bit after position @pos in bitmap @bitmap.
657  * @pos can be -1 to search for the first set bit. Position starts
658  * at 0.
659  *
660  * Returns the position of the found bit, or -1 if no bit found.
661  */
662 ssize_t
663 virBitmapNextClearBit(virBitmapPtr bitmap, ssize_t pos)
664 {
665     size_t nl;
666     size_t nb;
667     unsigned long bits;
668
669     if (pos < 0)
670         pos = -1;
671
672     pos++;
673
674     if (pos >= bitmap->max_bit)
675         return -1;
676
677     nl = pos / VIR_BITMAP_BITS_PER_UNIT;
678     nb = pos % VIR_BITMAP_BITS_PER_UNIT;
679
680     bits = ~bitmap->map[nl] & ~((1UL << nb) - 1);
681
682     while (bits == 0 && ++nl < bitmap->map_len) {
683         bits = ~bitmap->map[nl];
684     }
685
686     if (nl == bitmap->map_len - 1) {
687         /* Ensure tail bits are ignored.  */
688         int tail = bitmap->max_bit % VIR_BITMAP_BITS_PER_UNIT;
689
690         if (tail)
691             bits &= -1UL >> (VIR_BITMAP_BITS_PER_UNIT - tail);
692     }
693     if (bits == 0)
694         return -1;
695
696     return ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
697 }
698
699 /* Return the number of bits currently set in the map.  */
700 size_t
701 virBitmapCountBits(virBitmapPtr bitmap)
702 {
703     size_t i;
704     size_t ret = 0;
705
706     for (i = 0; i < bitmap->map_len; i++)
707         ret += count_one_bits_l(bitmap->map[i]);
708
709     return ret;
710 }