Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
bitmap.c
Go to the documentation of this file.
1 /*
2  * lib/bitmap.c
3  * Helper functions for bitmap.h.
4  *
5  * This source code is licensed under the GNU General Public License,
6  * Version 2. See the file COPYING for more details.
7  */
8 #include <linux/export.h>
9 #include <linux/thread_info.h>
10 #include <linux/ctype.h>
11 #include <linux/errno.h>
12 #include <linux/bitmap.h>
13 #include <linux/bitops.h>
14 #include <linux/bug.h>
15 #include <asm/uaccess.h>
16 
17 /*
18  * bitmaps provide an array of bits, implemented using an an
19  * array of unsigned longs. The number of valid bits in a
20  * given bitmap does _not_ need to be an exact multiple of
21  * BITS_PER_LONG.
22  *
23  * The possible unused bits in the last, partially used word
24  * of a bitmap are 'don't care'. The implementation makes
25  * no particular effort to keep them zero. It ensures that
26  * their value will not affect the results of any operation.
27  * The bitmap operations that return Boolean (bitmap_empty,
28  * for example) or scalar (bitmap_weight, for example) results
29  * carefully filter out these unused bits from impacting their
30  * results.
31  *
32  * These operations actually hold to a slightly stronger rule:
33  * if you don't input any bitmaps to these ops that have some
34  * unused bits set, then they won't output any set unused bits
35  * in output bitmaps.
36  *
37  * The byte ordering of bitmaps is more natural on little
38  * endian architectures. See the big-endian headers
39  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
40  * for the best explanations of this ordering.
41  */
42 
43 int __bitmap_empty(const unsigned long *bitmap, int bits)
44 {
45  int k, lim = bits/BITS_PER_LONG;
46  for (k = 0; k < lim; ++k)
47  if (bitmap[k])
48  return 0;
49 
50  if (bits % BITS_PER_LONG)
51  if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
52  return 0;
53 
54  return 1;
55 }
57 
58 int __bitmap_full(const unsigned long *bitmap, int bits)
59 {
60  int k, lim = bits/BITS_PER_LONG;
61  for (k = 0; k < lim; ++k)
62  if (~bitmap[k])
63  return 0;
64 
65  if (bits % BITS_PER_LONG)
66  if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
67  return 0;
68 
69  return 1;
70 }
72 
73 int __bitmap_equal(const unsigned long *bitmap1,
74  const unsigned long *bitmap2, int bits)
75 {
76  int k, lim = bits/BITS_PER_LONG;
77  for (k = 0; k < lim; ++k)
78  if (bitmap1[k] != bitmap2[k])
79  return 0;
80 
81  if (bits % BITS_PER_LONG)
82  if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
83  return 0;
84 
85  return 1;
86 }
88 
89 void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
90 {
91  int k, lim = bits/BITS_PER_LONG;
92  for (k = 0; k < lim; ++k)
93  dst[k] = ~src[k];
94 
95  if (bits % BITS_PER_LONG)
96  dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
97 }
99 
111 void __bitmap_shift_right(unsigned long *dst,
112  const unsigned long *src, int shift, int bits)
113 {
114  int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
115  int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
116  unsigned long mask = (1UL << left) - 1;
117  for (k = 0; off + k < lim; ++k) {
118  unsigned long upper, lower;
119 
120  /*
121  * If shift is not word aligned, take lower rem bits of
122  * word above and make them the top rem bits of result.
123  */
124  if (!rem || off + k + 1 >= lim)
125  upper = 0;
126  else {
127  upper = src[off + k + 1];
128  if (off + k + 1 == lim - 1 && left)
129  upper &= mask;
130  }
131  lower = src[off + k];
132  if (left && off + k == lim - 1)
133  lower &= mask;
134  dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
135  if (left && k == lim - 1)
136  dst[k] &= mask;
137  }
138  if (off)
139  memset(&dst[lim - off], 0, off*sizeof(unsigned long));
140 }
142 
143 
156 void __bitmap_shift_left(unsigned long *dst,
157  const unsigned long *src, int shift, int bits)
158 {
159  int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
160  int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
161  for (k = lim - off - 1; k >= 0; --k) {
162  unsigned long upper, lower;
163 
164  /*
165  * If shift is not word aligned, take upper rem bits of
166  * word below and make them the bottom rem bits of result.
167  */
168  if (rem && k > 0)
169  lower = src[k - 1];
170  else
171  lower = 0;
172  upper = src[k];
173  if (left && k == lim - 1)
174  upper &= (1UL << left) - 1;
175  dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem;
176  if (left && k + off == lim - 1)
177  dst[k + off] &= (1UL << left) - 1;
178  }
179  if (off)
180  memset(dst, 0, off*sizeof(unsigned long));
181 }
183 
184 int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
185  const unsigned long *bitmap2, int bits)
186 {
187  int k;
188  int nr = BITS_TO_LONGS(bits);
189  unsigned long result = 0;
190 
191  for (k = 0; k < nr; k++)
192  result |= (dst[k] = bitmap1[k] & bitmap2[k]);
193  return result != 0;
194 }
196 
197 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
198  const unsigned long *bitmap2, int bits)
199 {
200  int k;
201  int nr = BITS_TO_LONGS(bits);
202 
203  for (k = 0; k < nr; k++)
204  dst[k] = bitmap1[k] | bitmap2[k];
205 }
207 
208 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
209  const unsigned long *bitmap2, int bits)
210 {
211  int k;
212  int nr = BITS_TO_LONGS(bits);
213 
214  for (k = 0; k < nr; k++)
215  dst[k] = bitmap1[k] ^ bitmap2[k];
216 }
218 
219 int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
220  const unsigned long *bitmap2, int bits)
221 {
222  int k;
223  int nr = BITS_TO_LONGS(bits);
224  unsigned long result = 0;
225 
226  for (k = 0; k < nr; k++)
227  result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
228  return result != 0;
229 }
231 
232 int __bitmap_intersects(const unsigned long *bitmap1,
233  const unsigned long *bitmap2, int bits)
234 {
235  int k, lim = bits/BITS_PER_LONG;
236  for (k = 0; k < lim; ++k)
237  if (bitmap1[k] & bitmap2[k])
238  return 1;
239 
240  if (bits % BITS_PER_LONG)
241  if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
242  return 1;
243  return 0;
244 }
246 
247 int __bitmap_subset(const unsigned long *bitmap1,
248  const unsigned long *bitmap2, int bits)
249 {
250  int k, lim = bits/BITS_PER_LONG;
251  for (k = 0; k < lim; ++k)
252  if (bitmap1[k] & ~bitmap2[k])
253  return 0;
254 
255  if (bits % BITS_PER_LONG)
256  if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
257  return 0;
258  return 1;
259 }
261 
262 int __bitmap_weight(const unsigned long *bitmap, int bits)
263 {
264  int k, w = 0, lim = bits/BITS_PER_LONG;
265 
266  for (k = 0; k < lim; k++)
267  w += hweight_long(bitmap[k]);
268 
269  if (bits % BITS_PER_LONG)
270  w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
271 
272  return w;
273 }
275 
276 void bitmap_set(unsigned long *map, int start, int nr)
277 {
278  unsigned long *p = map + BIT_WORD(start);
279  const int size = start + nr;
280  int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
281  unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
282 
283  while (nr - bits_to_set >= 0) {
284  *p |= mask_to_set;
285  nr -= bits_to_set;
286  bits_to_set = BITS_PER_LONG;
287  mask_to_set = ~0UL;
288  p++;
289  }
290  if (nr) {
291  mask_to_set &= BITMAP_LAST_WORD_MASK(size);
292  *p |= mask_to_set;
293  }
294 }
296 
297 void bitmap_clear(unsigned long *map, int start, int nr)
298 {
299  unsigned long *p = map + BIT_WORD(start);
300  const int size = start + nr;
301  int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
302  unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
303 
304  while (nr - bits_to_clear >= 0) {
305  *p &= ~mask_to_clear;
306  nr -= bits_to_clear;
307  bits_to_clear = BITS_PER_LONG;
308  mask_to_clear = ~0UL;
309  p++;
310  }
311  if (nr) {
312  mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
313  *p &= ~mask_to_clear;
314  }
315 }
317 
318 /*
319  * bitmap_find_next_zero_area - find a contiguous aligned zero area
320  * @map: The address to base the search on
321  * @size: The bitmap size in bits
322  * @start: The bitnumber to start searching at
323  * @nr: The number of zeroed bits we're looking for
324  * @align_mask: Alignment mask for zero area
325  *
326  * The @align_mask should be one less than a power of 2; the effect is that
327  * the bit offset of all zero areas this function finds is multiples of that
328  * power of 2. A @align_mask of 0 means no alignment is required.
329  */
330 unsigned long bitmap_find_next_zero_area(unsigned long *map,
331  unsigned long size,
332  unsigned long start,
333  unsigned int nr,
334  unsigned long align_mask)
335 {
336  unsigned long index, end, i;
337 again:
338  index = find_next_zero_bit(map, size, start);
339 
340  /* Align allocation */
341  index = __ALIGN_MASK(index, align_mask);
342 
343  end = index + nr;
344  if (end > size)
345  return end;
346  i = find_next_bit(map, end, index);
347  if (i < end) {
348  start = i + 1;
349  goto again;
350  }
351  return index;
352 }
354 
355 /*
356  * Bitmap printing & parsing functions: first version by Bill Irwin,
357  * second version by Paul Jackson, third by Joe Korty.
358  */
359 
360 #define CHUNKSZ 32
361 #define nbits_to_hold_value(val) fls(val)
362 #define BASEDEC 10 /* fancier cpuset lists input in decimal */
363 
375 int bitmap_scnprintf(char *buf, unsigned int buflen,
376  const unsigned long *maskp, int nmaskbits)
377 {
378  int i, word, bit, len = 0;
379  unsigned long val;
380  const char *sep = "";
381  int chunksz;
382  u32 chunkmask;
383 
384  chunksz = nmaskbits & (CHUNKSZ - 1);
385  if (chunksz == 0)
386  chunksz = CHUNKSZ;
387 
388  i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ;
389  for (; i >= 0; i -= CHUNKSZ) {
390  chunkmask = ((1ULL << chunksz) - 1);
391  word = i / BITS_PER_LONG;
392  bit = i % BITS_PER_LONG;
393  val = (maskp[word] >> bit) & chunkmask;
394  len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
395  (chunksz+3)/4, val);
396  chunksz = CHUNKSZ;
397  sep = ",";
398  }
399  return len;
400 }
402 
419 int __bitmap_parse(const char *buf, unsigned int buflen,
420  int is_user, unsigned long *maskp,
421  int nmaskbits)
422 {
423  int c, old_c, totaldigits, ndigits, nchunks, nbits;
424  u32 chunk;
425  const char __user __force *ubuf = (const char __user __force *)buf;
426 
427  bitmap_zero(maskp, nmaskbits);
428 
429  nchunks = nbits = totaldigits = c = 0;
430  do {
431  chunk = ndigits = 0;
432 
433  /* Get the next chunk of the bitmap */
434  while (buflen) {
435  old_c = c;
436  if (is_user) {
437  if (__get_user(c, ubuf++))
438  return -EFAULT;
439  }
440  else
441  c = *buf++;
442  buflen--;
443  if (isspace(c))
444  continue;
445 
446  /*
447  * If the last character was a space and the current
448  * character isn't '\0', we've got embedded whitespace.
449  * This is a no-no, so throw an error.
450  */
451  if (totaldigits && c && isspace(old_c))
452  return -EINVAL;
453 
454  /* A '\0' or a ',' signal the end of the chunk */
455  if (c == '\0' || c == ',')
456  break;
457 
458  if (!isxdigit(c))
459  return -EINVAL;
460 
461  /*
462  * Make sure there are at least 4 free bits in 'chunk'.
463  * If not, this hexdigit will overflow 'chunk', so
464  * throw an error.
465  */
466  if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
467  return -EOVERFLOW;
468 
469  chunk = (chunk << 4) | hex_to_bin(c);
470  ndigits++; totaldigits++;
471  }
472  if (ndigits == 0)
473  return -EINVAL;
474  if (nchunks == 0 && chunk == 0)
475  continue;
476 
477  __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
478  *maskp |= chunk;
479  nchunks++;
480  nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
481  if (nbits > nmaskbits)
482  return -EOVERFLOW;
483  } while (buflen && c == ',');
484 
485  return 0;
486 }
488 
504 int bitmap_parse_user(const char __user *ubuf,
505  unsigned int ulen, unsigned long *maskp,
506  int nmaskbits)
507 {
508  if (!access_ok(VERIFY_READ, ubuf, ulen))
509  return -EFAULT;
510  return __bitmap_parse((const char __force *)ubuf,
511  ulen, 1, maskp, nmaskbits);
512 
513 }
515 
516 /*
517  * bscnl_emit(buf, buflen, rbot, rtop, bp)
518  *
519  * Helper routine for bitmap_scnlistprintf(). Write decimal number
520  * or range to buf, suppressing output past buf+buflen, with optional
521  * comma-prefix. Return len of what was written to *buf, excluding the
522  * trailing \0.
523  */
524 static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
525 {
526  if (len > 0)
527  len += scnprintf(buf + len, buflen - len, ",");
528  if (rbot == rtop)
529  len += scnprintf(buf + len, buflen - len, "%d", rbot);
530  else
531  len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
532  return len;
533 }
534 
551 int bitmap_scnlistprintf(char *buf, unsigned int buflen,
552  const unsigned long *maskp, int nmaskbits)
553 {
554  int len = 0;
555  /* current bit is 'cur', most recently seen range is [rbot, rtop] */
556  int cur, rbot, rtop;
557 
558  if (buflen == 0)
559  return 0;
560  buf[0] = 0;
561 
562  rbot = cur = find_first_bit(maskp, nmaskbits);
563  while (cur < nmaskbits) {
564  rtop = cur;
565  cur = find_next_bit(maskp, nmaskbits, cur+1);
566  if (cur >= nmaskbits || cur > rtop + 1) {
567  len = bscnl_emit(buf, buflen, rbot, rtop, len);
568  rbot = cur;
569  }
570  }
571  return len;
572 }
574 
595 static int __bitmap_parselist(const char *buf, unsigned int buflen,
596  int is_user, unsigned long *maskp,
597  int nmaskbits)
598 {
599  unsigned a, b;
600  int c, old_c, totaldigits;
601  const char __user __force *ubuf = (const char __user __force *)buf;
602  int exp_digit, in_range;
603 
604  totaldigits = c = 0;
605  bitmap_zero(maskp, nmaskbits);
606  do {
607  exp_digit = 1;
608  in_range = 0;
609  a = b = 0;
610 
611  /* Get the next cpu# or a range of cpu#'s */
612  while (buflen) {
613  old_c = c;
614  if (is_user) {
615  if (__get_user(c, ubuf++))
616  return -EFAULT;
617  } else
618  c = *buf++;
619  buflen--;
620  if (isspace(c))
621  continue;
622 
623  /*
624  * If the last character was a space and the current
625  * character isn't '\0', we've got embedded whitespace.
626  * This is a no-no, so throw an error.
627  */
628  if (totaldigits && c && isspace(old_c))
629  return -EINVAL;
630 
631  /* A '\0' or a ',' signal the end of a cpu# or range */
632  if (c == '\0' || c == ',')
633  break;
634 
635  if (c == '-') {
636  if (exp_digit || in_range)
637  return -EINVAL;
638  b = 0;
639  in_range = 1;
640  exp_digit = 1;
641  continue;
642  }
643 
644  if (!isdigit(c))
645  return -EINVAL;
646 
647  b = b * 10 + (c - '0');
648  if (!in_range)
649  a = b;
650  exp_digit = 0;
651  totaldigits++;
652  }
653  if (!(a <= b))
654  return -EINVAL;
655  if (b >= nmaskbits)
656  return -ERANGE;
657  while (a <= b) {
658  set_bit(a, maskp);
659  a++;
660  }
661  } while (buflen && c == ',');
662  return 0;
663 }
664 
665 int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
666 {
667  char *nl = strchr(bp, '\n');
668  int len;
669 
670  if (nl)
671  len = nl - bp;
672  else
673  len = strlen(bp);
674 
675  return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
676 }
678 
679 
695 int bitmap_parselist_user(const char __user *ubuf,
696  unsigned int ulen, unsigned long *maskp,
697  int nmaskbits)
698 {
699  if (!access_ok(VERIFY_READ, ubuf, ulen))
700  return -EFAULT;
701  return __bitmap_parselist((const char __force *)ubuf,
702  ulen, 1, maskp, nmaskbits);
703 }
705 
706 
725 static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
726 {
727  int i, ord;
728 
729  if (pos < 0 || pos >= bits || !test_bit(pos, buf))
730  return -1;
731 
732  i = find_first_bit(buf, bits);
733  ord = 0;
734  while (i < pos) {
735  i = find_next_bit(buf, bits, i + 1);
736  ord++;
737  }
738  BUG_ON(i != pos);
739 
740  return ord;
741 }
742 
761 int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
762 {
763  int pos = 0;
764 
765  if (ord >= 0 && ord < bits) {
766  int i;
767 
768  for (i = find_first_bit(buf, bits);
769  i < bits && ord > 0;
770  i = find_next_bit(buf, bits, i + 1))
771  ord--;
772  if (i < bits && ord == 0)
773  pos = i;
774  }
775 
776  return pos;
777 }
778 
811 void bitmap_remap(unsigned long *dst, const unsigned long *src,
812  const unsigned long *old, const unsigned long *new,
813  int bits)
814 {
815  int oldbit, w;
816 
817  if (dst == src) /* following doesn't handle inplace remaps */
818  return;
819  bitmap_zero(dst, bits);
820 
821  w = bitmap_weight(new, bits);
822  for_each_set_bit(oldbit, src, bits) {
823  int n = bitmap_pos_to_ord(old, oldbit, bits);
824 
825  if (n < 0 || w == 0)
826  set_bit(oldbit, dst); /* identity map */
827  else
828  set_bit(bitmap_ord_to_pos(new, n % w, bits), dst);
829  }
830 }
832 
859 int bitmap_bitremap(int oldbit, const unsigned long *old,
860  const unsigned long *new, int bits)
861 {
862  int w = bitmap_weight(new, bits);
863  int n = bitmap_pos_to_ord(old, oldbit, bits);
864  if (n < 0 || w == 0)
865  return oldbit;
866  else
867  return bitmap_ord_to_pos(new, n % w, bits);
868 }
870 
971 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
972  const unsigned long *relmap, int bits)
973 {
974  int n, m; /* same meaning as in above comment */
975 
976  if (dst == orig) /* following doesn't handle inplace mappings */
977  return;
978  bitmap_zero(dst, bits);
979 
980  /*
981  * The following code is a more efficient, but less
982  * obvious, equivalent to the loop:
983  * for (m = 0; m < bitmap_weight(relmap, bits); m++) {
984  * n = bitmap_ord_to_pos(orig, m, bits);
985  * if (test_bit(m, orig))
986  * set_bit(n, dst);
987  * }
988  */
989 
990  m = 0;
991  for_each_set_bit(n, relmap, bits) {
992  /* m == bitmap_pos_to_ord(relmap, n, bits) */
993  if (test_bit(m, orig))
994  set_bit(n, dst);
995  m++;
996  }
997 }
999 
1011 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
1012  int sz, int bits)
1013 {
1014  int oldbit;
1015 
1016  if (dst == orig) /* following doesn't handle inplace mappings */
1017  return;
1018  bitmap_zero(dst, bits);
1019 
1020  for_each_set_bit(oldbit, orig, bits)
1021  set_bit(oldbit % sz, dst);
1022 }
1024 
1025 /*
1026  * Common code for bitmap_*_region() routines.
1027  * bitmap: array of unsigned longs corresponding to the bitmap
1028  * pos: the beginning of the region
1029  * order: region size (log base 2 of number of bits)
1030  * reg_op: operation(s) to perform on that region of bitmap
1031  *
1032  * Can set, verify and/or release a region of bits in a bitmap,
1033  * depending on which combination of REG_OP_* flag bits is set.
1034  *
1035  * A region of a bitmap is a sequence of bits in the bitmap, of
1036  * some size '1 << order' (a power of two), aligned to that same
1037  * '1 << order' power of two.
1038  *
1039  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1040  * Returns 0 in all other cases and reg_ops.
1041  */
1042 
1043 enum {
1044  REG_OP_ISFREE, /* true if region is all zero bits */
1045  REG_OP_ALLOC, /* set all bits in region */
1046  REG_OP_RELEASE, /* clear all bits in region */
1047 };
1048 
1049 static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
1050 {
1051  int nbits_reg; /* number of bits in region */
1052  int index; /* index first long of region in bitmap */
1053  int offset; /* bit offset region in bitmap[index] */
1054  int nlongs_reg; /* num longs spanned by region in bitmap */
1055  int nbitsinlong; /* num bits of region in each spanned long */
1056  unsigned long mask; /* bitmask for one long of region */
1057  int i; /* scans bitmap by longs */
1058  int ret = 0; /* return value */
1059 
1060  /*
1061  * Either nlongs_reg == 1 (for small orders that fit in one long)
1062  * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
1063  */
1064  nbits_reg = 1 << order;
1065  index = pos / BITS_PER_LONG;
1066  offset = pos - (index * BITS_PER_LONG);
1067  nlongs_reg = BITS_TO_LONGS(nbits_reg);
1068  nbitsinlong = min(nbits_reg, BITS_PER_LONG);
1069 
1070  /*
1071  * Can't do "mask = (1UL << nbitsinlong) - 1", as that
1072  * overflows if nbitsinlong == BITS_PER_LONG.
1073  */
1074  mask = (1UL << (nbitsinlong - 1));
1075  mask += mask - 1;
1076  mask <<= offset;
1077 
1078  switch (reg_op) {
1079  case REG_OP_ISFREE:
1080  for (i = 0; i < nlongs_reg; i++) {
1081  if (bitmap[index + i] & mask)
1082  goto done;
1083  }
1084  ret = 1; /* all bits in region free (zero) */
1085  break;
1086 
1087  case REG_OP_ALLOC:
1088  for (i = 0; i < nlongs_reg; i++)
1089  bitmap[index + i] |= mask;
1090  break;
1091 
1092  case REG_OP_RELEASE:
1093  for (i = 0; i < nlongs_reg; i++)
1094  bitmap[index + i] &= ~mask;
1095  break;
1096  }
1097 done:
1098  return ret;
1099 }
1100 
1115 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
1116 {
1117  int pos, end; /* scans bitmap by regions of size order */
1118 
1119  for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
1120  if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1121  continue;
1122  __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1123  return pos;
1124  }
1125  return -ENOMEM;
1126 }
1128 
1140 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
1141 {
1142  __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1143 }
1145 
1157 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
1158 {
1159  if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1160  return -EBUSY;
1161  __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1162  return 0;
1163 }
1165 
1174 void bitmap_copy_le(void *dst, const unsigned long *src, int nbits)
1175 {
1176  unsigned long *d = dst;
1177  int i;
1178 
1179  for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1180  if (BITS_PER_LONG == 64)
1181  d[i] = cpu_to_le64(src[i]);
1182  else
1183  d[i] = cpu_to_le32(src[i]);
1184  }
1185 }