Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


Added Kitten
[palacios-OLD.git] / kitten / lib / bitmap.c
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 <lwk/kernel.h>
9 #include <lwk/ctype.h>
10 #include <lwk/errno.h>
11 #include <lwk/bitmap.h>
12 #include <lwk/bitops.h>
13 #include <lwk/linux_compat.h>
14 //#include <asm/uaccess.h>
15
16 /*
17  * bitmaps provide an array of bits, implemented using an an
18  * array of unsigned longs.  The number of valid bits in a
19  * given bitmap does _not_ need to be an exact multiple of
20  * BITS_PER_LONG.
21  *
22  * The possible unused bits in the last, partially used word
23  * of a bitmap are 'don't care'.  The implementation makes
24  * no particular effort to keep them zero.  It ensures that
25  * their value will not affect the results of any operation.
26  * The bitmap operations that return Boolean (bitmap_empty,
27  * for example) or scalar (bitmap_weight, for example) results
28  * carefully filter out these unused bits from impacting their
29  * results.
30  *
31  * These operations actually hold to a slightly stronger rule:
32  * if you don't input any bitmaps to these ops that have some
33  * unused bits set, then they won't output any set unused bits
34  * in output bitmaps.
35  *
36  * The byte ordering of bitmaps is more natural on little
37  * endian architectures.  See the big-endian headers
38  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
39  * for the best explanations of this ordering.
40  */
41
42 int __bitmap_empty(const unsigned long *bitmap, int bits)
43 {
44         int k, lim = bits/BITS_PER_LONG;
45         for (k = 0; k < lim; ++k)
46                 if (bitmap[k])
47                         return 0;
48
49         if (bits % BITS_PER_LONG)
50                 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
51                         return 0;
52
53         return 1;
54 }
55 EXPORT_SYMBOL(__bitmap_empty);
56
57 int __bitmap_full(const unsigned long *bitmap, int bits)
58 {
59         int k, lim = bits/BITS_PER_LONG;
60         for (k = 0; k < lim; ++k)
61                 if (~bitmap[k])
62                         return 0;
63
64         if (bits % BITS_PER_LONG)
65                 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
66                         return 0;
67
68         return 1;
69 }
70 EXPORT_SYMBOL(__bitmap_full);
71
72 int __bitmap_equal(const unsigned long *bitmap1,
73                 const unsigned long *bitmap2, int bits)
74 {
75         int k, lim = bits/BITS_PER_LONG;
76         for (k = 0; k < lim; ++k)
77                 if (bitmap1[k] != bitmap2[k])
78                         return 0;
79
80         if (bits % BITS_PER_LONG)
81                 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
82                         return 0;
83
84         return 1;
85 }
86 EXPORT_SYMBOL(__bitmap_equal);
87
88 void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
89 {
90         int k, lim = bits/BITS_PER_LONG;
91         for (k = 0; k < lim; ++k)
92                 dst[k] = ~src[k];
93
94         if (bits % BITS_PER_LONG)
95                 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
96 }
97 EXPORT_SYMBOL(__bitmap_complement);
98
99 /*
100  * __bitmap_shift_right - logical right shift of the bits in a bitmap
101  *   @dst - destination bitmap
102  *   @src - source bitmap
103  *   @nbits - shift by this many bits
104  *   @bits - bitmap size, in bits
105  *
106  * Shifting right (dividing) means moving bits in the MS -> LS bit
107  * direction.  Zeros are fed into the vacated MS positions and the
108  * LS bits shifted off the bottom are lost.
109  */
110 void __bitmap_shift_right(unsigned long *dst,
111                         const unsigned long *src, int shift, int bits)
112 {
113         int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
114         int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
115         unsigned long mask = (1UL << left) - 1;
116         for (k = 0; off + k < lim; ++k) {
117                 unsigned long upper, lower;
118
119                 /*
120                  * If shift is not word aligned, take lower rem bits of
121                  * word above and make them the top rem bits of result.
122                  */
123                 if (!rem || off + k + 1 >= lim)
124                         upper = 0;
125                 else {
126                         upper = src[off + k + 1];
127                         if (off + k + 1 == lim - 1 && left)
128                                 upper &= mask;
129                 }
130                 lower = src[off + k];
131                 if (left && off + k == lim - 1)
132                         lower &= mask;
133                 dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
134                 if (left && k == lim - 1)
135                         dst[k] &= mask;
136         }
137         if (off)
138                 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
139 }
140 EXPORT_SYMBOL(__bitmap_shift_right);
141
142
143 /*
144  * __bitmap_shift_left - logical left shift of the bits in a bitmap
145  *   @dst - destination bitmap
146  *   @src - source bitmap
147  *   @nbits - shift by this many bits
148  *   @bits - bitmap size, in bits
149  *
150  * Shifting left (multiplying) means moving bits in the LS -> MS
151  * direction.  Zeros are fed into the vacated LS bit positions
152  * and those MS bits shifted off the top are lost.
153  */
154
155 void __bitmap_shift_left(unsigned long *dst,
156                         const unsigned long *src, int shift, int bits)
157 {
158         int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
159         int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
160         for (k = lim - off - 1; k >= 0; --k) {
161                 unsigned long upper, lower;
162
163                 /*
164                  * If shift is not word aligned, take upper rem bits of
165                  * word below and make them the bottom rem bits of result.
166                  */
167                 if (rem && k > 0)
168                         lower = src[k - 1];
169                 else
170                         lower = 0;
171                 upper = src[k];
172                 if (left && k == lim - 1)
173                         upper &= (1UL << left) - 1;
174                 dst[k + off] = lower  >> (BITS_PER_LONG - rem) | upper << rem;
175                 if (left && k + off == lim - 1)
176                         dst[k + off] &= (1UL << left) - 1;
177         }
178         if (off)
179                 memset(dst, 0, off*sizeof(unsigned long));
180 }
181 EXPORT_SYMBOL(__bitmap_shift_left);
182
183 void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
184                                 const unsigned long *bitmap2, int bits)
185 {
186         int k;
187         int nr = BITS_TO_LONGS(bits);
188
189         for (k = 0; k < nr; k++)
190                 dst[k] = bitmap1[k] & bitmap2[k];
191 }
192 EXPORT_SYMBOL(__bitmap_and);
193
194 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
195                                 const unsigned long *bitmap2, int bits)
196 {
197         int k;
198         int nr = BITS_TO_LONGS(bits);
199
200         for (k = 0; k < nr; k++)
201                 dst[k] = bitmap1[k] | bitmap2[k];
202 }
203 EXPORT_SYMBOL(__bitmap_or);
204
205 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
206                                 const unsigned long *bitmap2, int bits)
207 {
208         int k;
209         int nr = BITS_TO_LONGS(bits);
210
211         for (k = 0; k < nr; k++)
212                 dst[k] = bitmap1[k] ^ bitmap2[k];
213 }
214 EXPORT_SYMBOL(__bitmap_xor);
215
216 void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
217                                 const unsigned long *bitmap2, int bits)
218 {
219         int k;
220         int nr = BITS_TO_LONGS(bits);
221
222         for (k = 0; k < nr; k++)
223                 dst[k] = bitmap1[k] & ~bitmap2[k];
224 }
225 EXPORT_SYMBOL(__bitmap_andnot);
226
227 int __bitmap_intersects(const unsigned long *bitmap1,
228                                 const unsigned long *bitmap2, int bits)
229 {
230         int k, lim = bits/BITS_PER_LONG;
231         for (k = 0; k < lim; ++k)
232                 if (bitmap1[k] & bitmap2[k])
233                         return 1;
234
235         if (bits % BITS_PER_LONG)
236                 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
237                         return 1;
238         return 0;
239 }
240 EXPORT_SYMBOL(__bitmap_intersects);
241
242 int __bitmap_subset(const unsigned long *bitmap1,
243                                 const unsigned long *bitmap2, int bits)
244 {
245         int k, lim = bits/BITS_PER_LONG;
246         for (k = 0; k < lim; ++k)
247                 if (bitmap1[k] & ~bitmap2[k])
248                         return 0;
249
250         if (bits % BITS_PER_LONG)
251                 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
252                         return 0;
253         return 1;
254 }
255 EXPORT_SYMBOL(__bitmap_subset);
256
257 int __bitmap_weight(const unsigned long *bitmap, int bits)
258 {
259         int k, w = 0, lim = bits/BITS_PER_LONG;
260
261         for (k = 0; k < lim; k++)
262                 w += hweight_long(bitmap[k]);
263
264         if (bits % BITS_PER_LONG)
265                 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
266
267         return w;
268 }
269 EXPORT_SYMBOL(__bitmap_weight);
270
271 /*
272  * Bitmap printing & parsing functions: first version by Bill Irwin,
273  * second version by Paul Jackson, third by Joe Korty.
274  */
275
276 #define CHUNKSZ                         32
277 #define nbits_to_hold_value(val)        fls(val)
278 #define unhex(c)                        (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
279 #define BASEDEC 10              /* fancier cpuset lists input in decimal */
280
281 /**
282  * bitmap_scnprintf - convert bitmap to an ASCII hex string.
283  * @buf: byte buffer into which string is placed
284  * @buflen: reserved size of @buf, in bytes
285  * @maskp: pointer to bitmap to convert
286  * @nmaskbits: size of bitmap, in bits
287  *
288  * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into
289  * comma-separated sets of eight digits per set.
290  */
291 int bitmap_scnprintf(char *buf, unsigned int buflen,
292         const unsigned long *maskp, int nmaskbits)
293 {
294         int i, word, bit, len = 0;
295         unsigned long val;
296         const char *sep = "";
297         int chunksz;
298         u32 chunkmask;
299
300         chunksz = nmaskbits & (CHUNKSZ - 1);
301         if (chunksz == 0)
302                 chunksz = CHUNKSZ;
303
304         i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ;
305         for (; i >= 0; i -= CHUNKSZ) {
306                 chunkmask = ((1ULL << chunksz) - 1);
307                 word = i / BITS_PER_LONG;
308                 bit = i % BITS_PER_LONG;
309                 val = (maskp[word] >> bit) & chunkmask;
310                 len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
311                         (chunksz+3)/4, val);
312                 chunksz = CHUNKSZ;
313                 sep = ",";
314         }
315         return len;
316 }
317 EXPORT_SYMBOL(bitmap_scnprintf);
318
319 #if 0
320 /**
321  * bitmap_parse - convert an ASCII hex string into a bitmap.
322  * @buf: pointer to buffer in user space containing string.
323  * @buflen: buffer size in bytes.  If string is smaller than this
324  *    then it must be terminated with a \0.
325  * @maskp: pointer to bitmap array that will contain result.
326  * @nmaskbits: size of bitmap, in bits.
327  *
328  * Commas group hex digits into chunks.  Each chunk defines exactly 32
329  * bits of the resultant bitmask.  No chunk may specify a value larger
330  * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
331  * then leading 0-bits are prepended.  -EINVAL is returned for illegal
332  * characters and for grouping errors such as "1,,5", ",44", "," and "".
333  * Leading and trailing whitespace accepted, but not embedded whitespace.
334  */
335 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
336         unsigned long *maskp, int nmaskbits)
337 {
338         int c, old_c, totaldigits, ndigits, nchunks, nbits;
339         u32 chunk;
340
341         bitmap_zero(maskp, nmaskbits);
342
343         nchunks = nbits = totaldigits = c = 0;
344         do {
345                 chunk = ndigits = 0;
346
347                 /* Get the next chunk of the bitmap */
348                 while (ubuflen) {
349                         old_c = c;
350                         if (get_user(c, ubuf++))
351                                 return -EFAULT;
352                         ubuflen--;
353                         if (isspace(c))
354                                 continue;
355
356                         /*
357                          * If the last character was a space and the current
358                          * character isn't '\0', we've got embedded whitespace.
359                          * This is a no-no, so throw an error.
360                          */
361                         if (totaldigits && c && isspace(old_c))
362                                 return -EINVAL;
363
364                         /* A '\0' or a ',' signal the end of the chunk */
365                         if (c == '\0' || c == ',')
366                                 break;
367
368                         if (!isxdigit(c))
369                                 return -EINVAL;
370
371                         /*
372                          * Make sure there are at least 4 free bits in 'chunk'.
373                          * If not, this hexdigit will overflow 'chunk', so
374                          * throw an error.
375                          */
376                         if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
377                                 return -EOVERFLOW;
378
379                         chunk = (chunk << 4) | unhex(c);
380                         ndigits++; totaldigits++;
381                 }
382                 if (ndigits == 0)
383                         return -EINVAL;
384                 if (nchunks == 0 && chunk == 0)
385                         continue;
386
387                 __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
388                 *maskp |= chunk;
389                 nchunks++;
390                 nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
391                 if (nbits > nmaskbits)
392                         return -EOVERFLOW;
393         } while (ubuflen && c == ',');
394
395         return 0;
396 }
397 EXPORT_SYMBOL(bitmap_parse);
398 #endif
399
400 /*
401  * bscnl_emit(buf, buflen, rbot, rtop, bp)
402  *
403  * Helper routine for bitmap_scnlistprintf().  Write decimal number
404  * or range to buf, suppressing output past buf+buflen, with optional
405  * comma-prefix.  Return len of what would be written to buf, if it
406  * all fit.
407  */
408 static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
409 {
410         if (len > 0)
411                 len += scnprintf(buf + len, buflen - len, ",");
412         if (rbot == rtop)
413                 len += scnprintf(buf + len, buflen - len, "%d", rbot);
414         else
415                 len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
416         return len;
417 }
418
419 /**
420  * bitmap_scnlistprintf - convert bitmap to list format ASCII string
421  * @buf: byte buffer into which string is placed
422  * @buflen: reserved size of @buf, in bytes
423  * @maskp: pointer to bitmap to convert
424  * @nmaskbits: size of bitmap, in bits
425  *
426  * Output format is a comma-separated list of decimal numbers and
427  * ranges.  Consecutively set bits are shown as two hyphen-separated
428  * decimal numbers, the smallest and largest bit numbers set in
429  * the range.  Output format is compatible with the format
430  * accepted as input by bitmap_parselist().
431  *
432  * The return value is the number of characters which would be
433  * generated for the given input, excluding the trailing '\0', as
434  * per ISO C99.
435  */
436 int bitmap_scnlistprintf(char *buf, unsigned int buflen,
437         const unsigned long *maskp, int nmaskbits)
438 {
439         int len = 0;
440         /* current bit is 'cur', most recently seen range is [rbot, rtop] */
441         int cur, rbot, rtop;
442
443         rbot = cur = find_first_bit(maskp, nmaskbits);
444         while (cur < nmaskbits) {
445                 rtop = cur;
446                 cur = find_next_bit(maskp, nmaskbits, cur+1);
447                 if (cur >= nmaskbits || cur > rtop + 1) {
448                         len = bscnl_emit(buf, buflen, rbot, rtop, len);
449                         rbot = cur;
450                 }
451         }
452         return len;
453 }
454 EXPORT_SYMBOL(bitmap_scnlistprintf);
455
456 /**
457  * bitmap_parselist - convert list format ASCII string to bitmap
458  * @buf: read nul-terminated user string from this buffer
459  * @mask: write resulting mask here
460  * @nmaskbits: number of bits in mask to be written
461  *
462  * Input format is a comma-separated list of decimal numbers and
463  * ranges.  Consecutively set bits are shown as two hyphen-separated
464  * decimal numbers, the smallest and largest bit numbers set in
465  * the range.
466  *
467  * Returns 0 on success, -errno on invalid input strings:
468  *    -EINVAL:   second number in range smaller than first
469  *    -EINVAL:   invalid character in string
470  *    -ERANGE:   bit number specified too large for mask
471  */
472 int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
473 {
474         unsigned a, b;
475
476         bitmap_zero(maskp, nmaskbits);
477         do {
478                 if (!isdigit(*bp))
479                         return -EINVAL;
480                 b = a = simple_strtoul(bp, (char **)&bp, BASEDEC);
481                 if (*bp == '-') {
482                         bp++;
483                         if (!isdigit(*bp))
484                                 return -EINVAL;
485                         b = simple_strtoul(bp, (char **)&bp, BASEDEC);
486                 }
487                 if (!(a <= b))
488                         return -EINVAL;
489                 if (b >= nmaskbits)
490                         return -ERANGE;
491                 while (a <= b) {
492                         set_bit(a, maskp);
493                         a++;
494                 }
495                 if (*bp == ',')
496                         bp++;
497         } while (*bp != '\0' && *bp != '\n');
498         return 0;
499 }
500 EXPORT_SYMBOL(bitmap_parselist);
501
502 /*
503  * bitmap_pos_to_ord(buf, pos, bits)
504  *      @buf: pointer to a bitmap
505  *      @pos: a bit position in @buf (0 <= @pos < @bits)
506  *      @bits: number of valid bit positions in @buf
507  *
508  * Map the bit at position @pos in @buf (of length @bits) to the
509  * ordinal of which set bit it is.  If it is not set or if @pos
510  * is not a valid bit position, map to -1.
511  *
512  * If for example, just bits 4 through 7 are set in @buf, then @pos
513  * values 4 through 7 will get mapped to 0 through 3, respectively,
514  * and other @pos values will get mapped to 0.  When @pos value 7
515  * gets mapped to (returns) @ord value 3 in this example, that means
516  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
517  *
518  * The bit positions 0 through @bits are valid positions in @buf.
519  */
520 static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
521 {
522         int i, ord;
523
524         if (pos < 0 || pos >= bits || !test_bit(pos, buf))
525                 return -1;
526
527         i = find_first_bit(buf, bits);
528         ord = 0;
529         while (i < pos) {
530                 i = find_next_bit(buf, bits, i + 1);
531                 ord++;
532         }
533         BUG_ON(i != pos);
534
535         return ord;
536 }
537
538 /**
539  * bitmap_ord_to_pos(buf, ord, bits)
540  *      @buf: pointer to bitmap
541  *      @ord: ordinal bit position (n-th set bit, n >= 0)
542  *      @bits: number of valid bit positions in @buf
543  *
544  * Map the ordinal offset of bit @ord in @buf to its position in @buf.
545  * Value of @ord should be in range 0 <= @ord < weight(buf), else
546  * results are undefined.
547  *
548  * If for example, just bits 4 through 7 are set in @buf, then @ord
549  * values 0 through 3 will get mapped to 4 through 7, respectively,
550  * and all other @ord values return undefined values.  When @ord value 3
551  * gets mapped to (returns) @pos value 7 in this example, that means
552  * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
553  *
554  * The bit positions 0 through @bits are valid positions in @buf.
555  */
556 static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
557 {
558         int pos = 0;
559
560         if (ord >= 0 && ord < bits) {
561                 int i;
562
563                 for (i = find_first_bit(buf, bits);
564                      i < bits && ord > 0;
565                      i = find_next_bit(buf, bits, i + 1))
566                         ord--;
567                 if (i < bits && ord == 0)
568                         pos = i;
569         }
570
571         return pos;
572 }
573
574 /**
575  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
576  *      @dst: remapped result
577  *      @src: subset to be remapped
578  *      @old: defines domain of map
579  *      @new: defines range of map
580  *      @bits: number of bits in each of these bitmaps
581  *
582  * Let @old and @new define a mapping of bit positions, such that
583  * whatever position is held by the n-th set bit in @old is mapped
584  * to the n-th set bit in @new.  In the more general case, allowing
585  * for the possibility that the weight 'w' of @new is less than the
586  * weight of @old, map the position of the n-th set bit in @old to
587  * the position of the m-th set bit in @new, where m == n % w.
588  *
589  * If either of the @old and @new bitmaps are empty, or if @src and
590  * @dst point to the same location, then this routine copies @src
591  * to @dst.
592  *
593  * The positions of unset bits in @old are mapped to themselves
594  * (the identify map).
595  *
596  * Apply the above specified mapping to @src, placing the result in
597  * @dst, clearing any bits previously set in @dst.
598  *
599  * For example, lets say that @old has bits 4 through 7 set, and
600  * @new has bits 12 through 15 set.  This defines the mapping of bit
601  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
602  * bit positions unchanged.  So if say @src comes into this routine
603  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
604  * 13 and 15 set.
605  */
606 void bitmap_remap(unsigned long *dst, const unsigned long *src,
607                 const unsigned long *old, const unsigned long *new,
608                 int bits)
609 {
610         int oldbit, w;
611
612         if (dst == src)         /* following doesn't handle inplace remaps */
613                 return;
614         bitmap_zero(dst, bits);
615
616         w = bitmap_weight(new, bits);
617         for (oldbit = find_first_bit(src, bits);
618              oldbit < bits;
619              oldbit = find_next_bit(src, bits, oldbit + 1)) {
620                 int n = bitmap_pos_to_ord(old, oldbit, bits);
621                 if (n < 0 || w == 0)
622                         set_bit(oldbit, dst);   /* identity map */
623                 else
624                         set_bit(bitmap_ord_to_pos(new, n % w, bits), dst);
625         }
626 }
627 EXPORT_SYMBOL(bitmap_remap);
628
629 /**
630  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
631  *      @oldbit - bit position to be mapped
632  *      @old: defines domain of map
633  *      @new: defines range of map
634  *      @bits: number of bits in each of these bitmaps
635  *
636  * Let @old and @new define a mapping of bit positions, such that
637  * whatever position is held by the n-th set bit in @old is mapped
638  * to the n-th set bit in @new.  In the more general case, allowing
639  * for the possibility that the weight 'w' of @new is less than the
640  * weight of @old, map the position of the n-th set bit in @old to
641  * the position of the m-th set bit in @new, where m == n % w.
642  *
643  * The positions of unset bits in @old are mapped to themselves
644  * (the identify map).
645  *
646  * Apply the above specified mapping to bit position @oldbit, returning
647  * the new bit position.
648  *
649  * For example, lets say that @old has bits 4 through 7 set, and
650  * @new has bits 12 through 15 set.  This defines the mapping of bit
651  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
652  * bit positions unchanged.  So if say @oldbit is 5, then this routine
653  * returns 13.
654  */
655 int bitmap_bitremap(int oldbit, const unsigned long *old,
656                                 const unsigned long *new, int bits)
657 {
658         int w = bitmap_weight(new, bits);
659         int n = bitmap_pos_to_ord(old, oldbit, bits);
660         if (n < 0 || w == 0)
661                 return oldbit;
662         else
663                 return bitmap_ord_to_pos(new, n % w, bits);
664 }
665 EXPORT_SYMBOL(bitmap_bitremap);
666
667 /*
668  * Common code for bitmap_*_region() routines.
669  *      bitmap: array of unsigned longs corresponding to the bitmap
670  *      pos: the beginning of the region
671  *      order: region size (log base 2 of number of bits)
672  *      reg_op: operation(s) to perform on that region of bitmap
673  *
674  * Can set, verify and/or release a region of bits in a bitmap,
675  * depending on which combination of REG_OP_* flag bits is set.
676  *
677  * A region of a bitmap is a sequence of bits in the bitmap, of
678  * some size '1 << order' (a power of two), aligned to that same
679  * '1 << order' power of two.
680  *
681  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
682  * Returns 0 in all other cases and reg_ops.
683  */
684
685 enum {
686         REG_OP_ISFREE,          /* true if region is all zero bits */
687         REG_OP_ALLOC,           /* set all bits in region */
688         REG_OP_RELEASE,         /* clear all bits in region */
689 };
690
691 static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
692 {
693         int nbits_reg;          /* number of bits in region */
694         int index;              /* index first long of region in bitmap */
695         int offset;             /* bit offset region in bitmap[index] */
696         int nlongs_reg;         /* num longs spanned by region in bitmap */
697         int nbitsinlong;        /* num bits of region in each spanned long */
698         unsigned long mask;     /* bitmask for one long of region */
699         int i;                  /* scans bitmap by longs */
700         int ret = 0;            /* return value */
701
702         /*
703          * Either nlongs_reg == 1 (for small orders that fit in one long)
704          * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
705          */
706         nbits_reg = 1 << order;
707         index = pos / BITS_PER_LONG;
708         offset = pos - (index * BITS_PER_LONG);
709         nlongs_reg = BITS_TO_LONGS(nbits_reg);
710         nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
711
712         /*
713          * Can't do "mask = (1UL << nbitsinlong) - 1", as that
714          * overflows if nbitsinlong == BITS_PER_LONG.
715          */
716         mask = (1UL << (nbitsinlong - 1));
717         mask += mask - 1;
718         mask <<= offset;
719
720         switch (reg_op) {
721         case REG_OP_ISFREE:
722                 for (i = 0; i < nlongs_reg; i++) {
723                         if (bitmap[index + i] & mask)
724                                 goto done;
725                 }
726                 ret = 1;        /* all bits in region free (zero) */
727                 break;
728
729         case REG_OP_ALLOC:
730                 for (i = 0; i < nlongs_reg; i++)
731                         bitmap[index + i] |= mask;
732                 break;
733
734         case REG_OP_RELEASE:
735                 for (i = 0; i < nlongs_reg; i++)
736                         bitmap[index + i] &= ~mask;
737                 break;
738         }
739 done:
740         return ret;
741 }
742
743 /**
744  * bitmap_find_free_region - find a contiguous aligned mem region
745  *      @bitmap: array of unsigned longs corresponding to the bitmap
746  *      @bits: number of bits in the bitmap
747  *      @order: region size (log base 2 of number of bits) to find
748  *
749  * Find a region of free (zero) bits in a @bitmap of @bits bits and
750  * allocate them (set them to one).  Only consider regions of length
751  * a power (@order) of two, aligned to that power of two, which
752  * makes the search algorithm much faster.
753  *
754  * Return the bit offset in bitmap of the allocated region,
755  * or -errno on failure.
756  */
757 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
758 {
759         int pos;                /* scans bitmap by regions of size order */
760
761         for (pos = 0; pos < bits; pos += (1 << order))
762                 if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
763                         break;
764         if (pos == bits)
765                 return -ENOMEM;
766         __reg_op(bitmap, pos, order, REG_OP_ALLOC);
767         return pos;
768 }
769 EXPORT_SYMBOL(bitmap_find_free_region);
770
771 /**
772  * bitmap_release_region - release allocated bitmap region
773  *      @bitmap: array of unsigned longs corresponding to the bitmap
774  *      @pos: beginning of bit region to release
775  *      @order: region size (log base 2 of number of bits) to release
776  *
777  * This is the complement to __bitmap_find_free_region and releases
778  * the found region (by clearing it in the bitmap).
779  *
780  * No return value.
781  */
782 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
783 {
784         __reg_op(bitmap, pos, order, REG_OP_RELEASE);
785 }
786 EXPORT_SYMBOL(bitmap_release_region);
787
788 /**
789  * bitmap_allocate_region - allocate bitmap region
790  *      @bitmap: array of unsigned longs corresponding to the bitmap
791  *      @pos: beginning of bit region to allocate
792  *      @order: region size (log base 2 of number of bits) to allocate
793  *
794  * Allocate (set bits in) a specified region of a bitmap.
795  *
796  * Return 0 on success, or -EBUSY if specified region wasn't
797  * free (not all bits were zero).
798  */
799 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
800 {
801         if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
802                 return -EBUSY;
803         __reg_op(bitmap, pos, order, REG_OP_ALLOC);
804         return 0;
805 }
806 EXPORT_SYMBOL(bitmap_allocate_region);