1
2
3
4
5
6
7#include <linux/bitmap.h>
8#include <linux/bitops.h>
9#include <linux/bug.h>
10#include <linux/ctype.h>
11#include <linux/device.h>
12#include <linux/errno.h>
13#include <linux/export.h>
14#include <linux/kernel.h>
15#include <linux/mm.h>
16#include <linux/slab.h>
17#include <linux/string.h>
18#include <linux/thread_info.h>
19#include <linux/uaccess.h>
20
21#include <asm/page.h>
22
23#include "kstrtox.h"
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48int __bitmap_equal(const unsigned long *bitmap1,
49 const unsigned long *bitmap2, unsigned int bits)
50{
51 unsigned int k, lim = bits/BITS_PER_LONG;
52 for (k = 0; k < lim; ++k)
53 if (bitmap1[k] != bitmap2[k])
54 return 0;
55
56 if (bits % BITS_PER_LONG)
57 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
58 return 0;
59
60 return 1;
61}
62EXPORT_SYMBOL(__bitmap_equal);
63
64bool __bitmap_or_equal(const unsigned long *bitmap1,
65 const unsigned long *bitmap2,
66 const unsigned long *bitmap3,
67 unsigned int bits)
68{
69 unsigned int k, lim = bits / BITS_PER_LONG;
70 unsigned long tmp;
71
72 for (k = 0; k < lim; ++k) {
73 if ((bitmap1[k] | bitmap2[k]) != bitmap3[k])
74 return false;
75 }
76
77 if (!(bits % BITS_PER_LONG))
78 return true;
79
80 tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k];
81 return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;
82}
83
84void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
85{
86 unsigned int k, lim = BITS_TO_LONGS(bits);
87 for (k = 0; k < lim; ++k)
88 dst[k] = ~src[k];
89}
90EXPORT_SYMBOL(__bitmap_complement);
91
92
93
94
95
96
97
98
99
100
101
102
103void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
104 unsigned shift, unsigned nbits)
105{
106 unsigned k, lim = BITS_TO_LONGS(nbits);
107 unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
108 unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
109 for (k = 0; off + k < lim; ++k) {
110 unsigned long upper, lower;
111
112
113
114
115
116 if (!rem || off + k + 1 >= lim)
117 upper = 0;
118 else {
119 upper = src[off + k + 1];
120 if (off + k + 1 == lim - 1)
121 upper &= mask;
122 upper <<= (BITS_PER_LONG - rem);
123 }
124 lower = src[off + k];
125 if (off + k == lim - 1)
126 lower &= mask;
127 lower >>= rem;
128 dst[k] = lower | upper;
129 }
130 if (off)
131 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
132}
133EXPORT_SYMBOL(__bitmap_shift_right);
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
149 unsigned int shift, unsigned int nbits)
150{
151 int k;
152 unsigned int lim = BITS_TO_LONGS(nbits);
153 unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
154 for (k = lim - off - 1; k >= 0; --k) {
155 unsigned long upper, lower;
156
157
158
159
160
161 if (rem && k > 0)
162 lower = src[k - 1] >> (BITS_PER_LONG - rem);
163 else
164 lower = 0;
165 upper = src[k] << rem;
166 dst[k + off] = lower | upper;
167 }
168 if (off)
169 memset(dst, 0, off*sizeof(unsigned long));
170}
171EXPORT_SYMBOL(__bitmap_shift_left);
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210void bitmap_cut(unsigned long *dst, const unsigned long *src,
211 unsigned int first, unsigned int cut, unsigned int nbits)
212{
213 unsigned int len = BITS_TO_LONGS(nbits);
214 unsigned long keep = 0, carry;
215 int i;
216
217 if (first % BITS_PER_LONG) {
218 keep = src[first / BITS_PER_LONG] &
219 (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));
220 }
221
222 memmove(dst, src, len * sizeof(*dst));
223
224 while (cut--) {
225 for (i = first / BITS_PER_LONG; i < len; i++) {
226 if (i < len - 1)
227 carry = dst[i + 1] & 1UL;
228 else
229 carry = 0;
230
231 dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));
232 }
233 }
234
235 dst[first / BITS_PER_LONG] &= ~0UL << (first % BITS_PER_LONG);
236 dst[first / BITS_PER_LONG] |= keep;
237}
238EXPORT_SYMBOL(bitmap_cut);
239
240int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
241 const unsigned long *bitmap2, unsigned int bits)
242{
243 unsigned int k;
244 unsigned int lim = bits/BITS_PER_LONG;
245 unsigned long result = 0;
246
247 for (k = 0; k < lim; k++)
248 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
249 if (bits % BITS_PER_LONG)
250 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
251 BITMAP_LAST_WORD_MASK(bits));
252 return result != 0;
253}
254EXPORT_SYMBOL(__bitmap_and);
255
256void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
257 const unsigned long *bitmap2, unsigned int bits)
258{
259 unsigned int k;
260 unsigned int nr = BITS_TO_LONGS(bits);
261
262 for (k = 0; k < nr; k++)
263 dst[k] = bitmap1[k] | bitmap2[k];
264}
265EXPORT_SYMBOL(__bitmap_or);
266
267void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
268 const unsigned long *bitmap2, unsigned int bits)
269{
270 unsigned int k;
271 unsigned int nr = BITS_TO_LONGS(bits);
272
273 for (k = 0; k < nr; k++)
274 dst[k] = bitmap1[k] ^ bitmap2[k];
275}
276EXPORT_SYMBOL(__bitmap_xor);
277
278int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
279 const unsigned long *bitmap2, unsigned int bits)
280{
281 unsigned int k;
282 unsigned int lim = bits/BITS_PER_LONG;
283 unsigned long result = 0;
284
285 for (k = 0; k < lim; k++)
286 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
287 if (bits % BITS_PER_LONG)
288 result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
289 BITMAP_LAST_WORD_MASK(bits));
290 return result != 0;
291}
292EXPORT_SYMBOL(__bitmap_andnot);
293
294void __bitmap_replace(unsigned long *dst,
295 const unsigned long *old, const unsigned long *new,
296 const unsigned long *mask, unsigned int nbits)
297{
298 unsigned int k;
299 unsigned int nr = BITS_TO_LONGS(nbits);
300
301 for (k = 0; k < nr; k++)
302 dst[k] = (old[k] & ~mask[k]) | (new[k] & mask[k]);
303}
304EXPORT_SYMBOL(__bitmap_replace);
305
306int __bitmap_intersects(const unsigned long *bitmap1,
307 const unsigned long *bitmap2, unsigned int bits)
308{
309 unsigned int k, lim = bits/BITS_PER_LONG;
310 for (k = 0; k < lim; ++k)
311 if (bitmap1[k] & bitmap2[k])
312 return 1;
313
314 if (bits % BITS_PER_LONG)
315 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
316 return 1;
317 return 0;
318}
319EXPORT_SYMBOL(__bitmap_intersects);
320
321int __bitmap_subset(const unsigned long *bitmap1,
322 const unsigned long *bitmap2, unsigned int bits)
323{
324 unsigned int k, lim = bits/BITS_PER_LONG;
325 for (k = 0; k < lim; ++k)
326 if (bitmap1[k] & ~bitmap2[k])
327 return 0;
328
329 if (bits % BITS_PER_LONG)
330 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
331 return 0;
332 return 1;
333}
334EXPORT_SYMBOL(__bitmap_subset);
335
336int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
337{
338 unsigned int k, lim = bits/BITS_PER_LONG;
339 int w = 0;
340
341 for (k = 0; k < lim; k++)
342 w += hweight_long(bitmap[k]);
343
344 if (bits % BITS_PER_LONG)
345 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
346
347 return w;
348}
349EXPORT_SYMBOL(__bitmap_weight);
350
351void __bitmap_set(unsigned long *map, unsigned int start, int len)
352{
353 unsigned long *p = map + BIT_WORD(start);
354 const unsigned int size = start + len;
355 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
356 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
357
358 while (len - bits_to_set >= 0) {
359 *p |= mask_to_set;
360 len -= bits_to_set;
361 bits_to_set = BITS_PER_LONG;
362 mask_to_set = ~0UL;
363 p++;
364 }
365 if (len) {
366 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
367 *p |= mask_to_set;
368 }
369}
370EXPORT_SYMBOL(__bitmap_set);
371
372void __bitmap_clear(unsigned long *map, unsigned int start, int len)
373{
374 unsigned long *p = map + BIT_WORD(start);
375 const unsigned int size = start + len;
376 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
377 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
378
379 while (len - bits_to_clear >= 0) {
380 *p &= ~mask_to_clear;
381 len -= bits_to_clear;
382 bits_to_clear = BITS_PER_LONG;
383 mask_to_clear = ~0UL;
384 p++;
385 }
386 if (len) {
387 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
388 *p &= ~mask_to_clear;
389 }
390}
391EXPORT_SYMBOL(__bitmap_clear);
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
407 unsigned long size,
408 unsigned long start,
409 unsigned int nr,
410 unsigned long align_mask,
411 unsigned long align_offset)
412{
413 unsigned long index, end, i;
414again:
415 index = find_next_zero_bit(map, size, start);
416
417
418 index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
419
420 end = index + nr;
421 if (end > size)
422 return end;
423 i = find_next_bit(map, end, index);
424 if (i < end) {
425 start = i + 1;
426 goto again;
427 }
428 return index;
429}
430EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446int bitmap_parse_user(const char __user *ubuf,
447 unsigned int ulen, unsigned long *maskp,
448 int nmaskbits)
449{
450 char *buf;
451 int ret;
452
453 buf = memdup_user_nul(ubuf, ulen);
454 if (IS_ERR(buf))
455 return PTR_ERR(buf);
456
457 ret = bitmap_parse(buf, UINT_MAX, maskp, nmaskbits);
458
459 kfree(buf);
460 return ret;
461}
462EXPORT_SYMBOL(bitmap_parse_user);
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
481 int nmaskbits)
482{
483 ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);
484
485 return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
486 scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
487}
488EXPORT_SYMBOL(bitmap_print_to_pagebuf);
489
490
491
492
493
494
495
496
497struct region {
498 unsigned int start;
499 unsigned int off;
500 unsigned int group_len;
501 unsigned int end;
502 unsigned int nbits;
503};
504
505static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
506{
507 unsigned int start;
508
509 for (start = r->start; start <= r->end; start += r->group_len)
510 bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
511}
512
513static int bitmap_check_region(const struct region *r)
514{
515 if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
516 return -EINVAL;
517
518 if (r->end >= r->nbits)
519 return -ERANGE;
520
521 return 0;
522}
523
524static const char *bitmap_getnum(const char *str, unsigned int *num,
525 unsigned int lastbit)
526{
527 unsigned long long n;
528 unsigned int len;
529
530 if (str[0] == 'N') {
531 *num = lastbit;
532 return str + 1;
533 }
534
535 len = _parse_integer(str, 10, &n);
536 if (!len)
537 return ERR_PTR(-EINVAL);
538 if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
539 return ERR_PTR(-EOVERFLOW);
540
541 *num = n;
542 return str + len;
543}
544
545static inline bool end_of_str(char c)
546{
547 return c == '\0' || c == '\n';
548}
549
550static inline bool __end_of_region(char c)
551{
552 return isspace(c) || c == ',';
553}
554
555static inline bool end_of_region(char c)
556{
557 return __end_of_region(c) || end_of_str(c);
558}
559
560
561
562
563
564static const char *bitmap_find_region(const char *str)
565{
566 while (__end_of_region(*str))
567 str++;
568
569 return end_of_str(*str) ? NULL : str;
570}
571
572static const char *bitmap_find_region_reverse(const char *start, const char *end)
573{
574 while (start <= end && __end_of_region(*end))
575 end--;
576
577 return end;
578}
579
580static const char *bitmap_parse_region(const char *str, struct region *r)
581{
582 unsigned int lastbit = r->nbits - 1;
583
584 if (!strncasecmp(str, "all", 3)) {
585 r->start = 0;
586 r->end = lastbit;
587 str += 3;
588
589 goto check_pattern;
590 }
591
592 str = bitmap_getnum(str, &r->start, lastbit);
593 if (IS_ERR(str))
594 return str;
595
596 if (end_of_region(*str))
597 goto no_end;
598
599 if (*str != '-')
600 return ERR_PTR(-EINVAL);
601
602 str = bitmap_getnum(str + 1, &r->end, lastbit);
603 if (IS_ERR(str))
604 return str;
605
606check_pattern:
607 if (end_of_region(*str))
608 goto no_pattern;
609
610 if (*str != ':')
611 return ERR_PTR(-EINVAL);
612
613 str = bitmap_getnum(str + 1, &r->off, lastbit);
614 if (IS_ERR(str))
615 return str;
616
617 if (*str != '/')
618 return ERR_PTR(-EINVAL);
619
620 return bitmap_getnum(str + 1, &r->group_len, lastbit);
621
622no_end:
623 r->end = r->start;
624no_pattern:
625 r->off = r->end + 1;
626 r->group_len = r->end + 1;
627
628 return end_of_str(*str) ? NULL : str;
629}
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
660{
661 struct region r;
662 long ret;
663
664 r.nbits = nmaskbits;
665 bitmap_zero(maskp, r.nbits);
666
667 while (buf) {
668 buf = bitmap_find_region(buf);
669 if (buf == NULL)
670 return 0;
671
672 buf = bitmap_parse_region(buf, &r);
673 if (IS_ERR(buf))
674 return PTR_ERR(buf);
675
676 ret = bitmap_check_region(&r);
677 if (ret)
678 return ret;
679
680 bitmap_set_region(&r, maskp);
681 }
682
683 return 0;
684}
685EXPORT_SYMBOL(bitmap_parselist);
686
687
688
689
690
691
692
693
694
695
696
697
698
699int bitmap_parselist_user(const char __user *ubuf,
700 unsigned int ulen, unsigned long *maskp,
701 int nmaskbits)
702{
703 char *buf;
704 int ret;
705
706 buf = memdup_user_nul(ubuf, ulen);
707 if (IS_ERR(buf))
708 return PTR_ERR(buf);
709
710 ret = bitmap_parselist(buf, maskp, nmaskbits);
711
712 kfree(buf);
713 return ret;
714}
715EXPORT_SYMBOL(bitmap_parselist_user);
716
717static const char *bitmap_get_x32_reverse(const char *start,
718 const char *end, u32 *num)
719{
720 u32 ret = 0;
721 int c, i;
722
723 for (i = 0; i < 32; i += 4) {
724 c = hex_to_bin(*end--);
725 if (c < 0)
726 return ERR_PTR(-EINVAL);
727
728 ret |= c << i;
729
730 if (start > end || __end_of_region(*end))
731 goto out;
732 }
733
734 if (hex_to_bin(*end--) >= 0)
735 return ERR_PTR(-EOVERFLOW);
736out:
737 *num = ret;
738 return end;
739}
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757int bitmap_parse(const char *start, unsigned int buflen,
758 unsigned long *maskp, int nmaskbits)
759{
760 const char *end = strnchrnul(start, buflen, '\n') - 1;
761 int chunks = BITS_TO_U32(nmaskbits);
762 u32 *bitmap = (u32 *)maskp;
763 int unset_bit;
764 int chunk;
765
766 for (chunk = 0; ; chunk++) {
767 end = bitmap_find_region_reverse(start, end);
768 if (start > end)
769 break;
770
771 if (!chunks--)
772 return -EOVERFLOW;
773
774#if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
775 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
776#else
777 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
778#endif
779 if (IS_ERR(end))
780 return PTR_ERR(end);
781 }
782
783 unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
784 if (unset_bit < nmaskbits) {
785 bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
786 return 0;
787 }
788
789 if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
790 return -EOVERFLOW;
791
792 return 0;
793}
794EXPORT_SYMBOL(bitmap_parse);
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
815{
816 if (pos >= nbits || !test_bit(pos, buf))
817 return -1;
818
819 return __bitmap_weight(buf, pos);
820}
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
841{
842 unsigned int pos;
843
844 for (pos = find_first_bit(buf, nbits);
845 pos < nbits && ord;
846 pos = find_next_bit(buf, nbits, pos + 1))
847 ord--;
848
849 return pos;
850}
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884void bitmap_remap(unsigned long *dst, const unsigned long *src,
885 const unsigned long *old, const unsigned long *new,
886 unsigned int nbits)
887{
888 unsigned int oldbit, w;
889
890 if (dst == src)
891 return;
892 bitmap_zero(dst, nbits);
893
894 w = bitmap_weight(new, nbits);
895 for_each_set_bit(oldbit, src, nbits) {
896 int n = bitmap_pos_to_ord(old, oldbit, nbits);
897
898 if (n < 0 || w == 0)
899 set_bit(oldbit, dst);
900 else
901 set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
902 }
903}
904EXPORT_SYMBOL(bitmap_remap);
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932int bitmap_bitremap(int oldbit, const unsigned long *old,
933 const unsigned long *new, int bits)
934{
935 int w = bitmap_weight(new, bits);
936 int n = bitmap_pos_to_ord(old, oldbit, bits);
937 if (n < 0 || w == 0)
938 return oldbit;
939 else
940 return bitmap_ord_to_pos(new, n % w, bits);
941}
942EXPORT_SYMBOL(bitmap_bitremap);
943
944#ifdef CONFIG_NUMA
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051void bitmap_onto(unsigned long *dst, const unsigned long *orig,
1052 const unsigned long *relmap, unsigned int bits)
1053{
1054 unsigned int n, m;
1055
1056 if (dst == orig)
1057 return;
1058 bitmap_zero(dst, bits);
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070 m = 0;
1071 for_each_set_bit(n, relmap, bits) {
1072
1073 if (test_bit(m, orig))
1074 set_bit(n, dst);
1075 m++;
1076 }
1077}
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090void bitmap_fold(unsigned long *dst, const unsigned long *orig,
1091 unsigned int sz, unsigned int nbits)
1092{
1093 unsigned int oldbit;
1094
1095 if (dst == orig)
1096 return;
1097 bitmap_zero(dst, nbits);
1098
1099 for_each_set_bit(oldbit, orig, nbits)
1100 set_bit(oldbit % sz, dst);
1101}
1102#endif
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122enum {
1123 REG_OP_ISFREE,
1124 REG_OP_ALLOC,
1125 REG_OP_RELEASE,
1126};
1127
1128static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1129{
1130 int nbits_reg;
1131 int index;
1132 int offset;
1133 int nlongs_reg;
1134 int nbitsinlong;
1135 unsigned long mask;
1136 int i;
1137 int ret = 0;
1138
1139
1140
1141
1142
1143 nbits_reg = 1 << order;
1144 index = pos / BITS_PER_LONG;
1145 offset = pos - (index * BITS_PER_LONG);
1146 nlongs_reg = BITS_TO_LONGS(nbits_reg);
1147 nbitsinlong = min(nbits_reg, BITS_PER_LONG);
1148
1149
1150
1151
1152
1153 mask = (1UL << (nbitsinlong - 1));
1154 mask += mask - 1;
1155 mask <<= offset;
1156
1157 switch (reg_op) {
1158 case REG_OP_ISFREE:
1159 for (i = 0; i < nlongs_reg; i++) {
1160 if (bitmap[index + i] & mask)
1161 goto done;
1162 }
1163 ret = 1;
1164 break;
1165
1166 case REG_OP_ALLOC:
1167 for (i = 0; i < nlongs_reg; i++)
1168 bitmap[index + i] |= mask;
1169 break;
1170
1171 case REG_OP_RELEASE:
1172 for (i = 0; i < nlongs_reg; i++)
1173 bitmap[index + i] &= ~mask;
1174 break;
1175 }
1176done:
1177 return ret;
1178}
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1195{
1196 unsigned int pos, end;
1197
1198 for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1199 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1200 continue;
1201 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1202 return pos;
1203 }
1204 return -ENOMEM;
1205}
1206EXPORT_SYMBOL(bitmap_find_free_region);
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1220{
1221 __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1222}
1223EXPORT_SYMBOL(bitmap_release_region);
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1237{
1238 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1239 return -EBUSY;
1240 return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1241}
1242EXPORT_SYMBOL(bitmap_allocate_region);
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252#ifdef __BIG_ENDIAN
1253void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
1254{
1255 unsigned int i;
1256
1257 for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1258 if (BITS_PER_LONG == 64)
1259 dst[i] = cpu_to_le64(src[i]);
1260 else
1261 dst[i] = cpu_to_le32(src[i]);
1262 }
1263}
1264EXPORT_SYMBOL(bitmap_copy_le);
1265#endif
1266
1267unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
1268{
1269 return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1270 flags);
1271}
1272EXPORT_SYMBOL(bitmap_alloc);
1273
1274unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
1275{
1276 return bitmap_alloc(nbits, flags | __GFP_ZERO);
1277}
1278EXPORT_SYMBOL(bitmap_zalloc);
1279
1280void bitmap_free(const unsigned long *bitmap)
1281{
1282 kfree(bitmap);
1283}
1284EXPORT_SYMBOL(bitmap_free);
1285
1286static void devm_bitmap_free(void *data)
1287{
1288 unsigned long *bitmap = data;
1289
1290 bitmap_free(bitmap);
1291}
1292
1293unsigned long *devm_bitmap_alloc(struct device *dev,
1294 unsigned int nbits, gfp_t flags)
1295{
1296 unsigned long *bitmap;
1297 int ret;
1298
1299 bitmap = bitmap_alloc(nbits, flags);
1300 if (!bitmap)
1301 return NULL;
1302
1303 ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
1304 if (ret)
1305 return NULL;
1306
1307 return bitmap;
1308}
1309EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
1310
1311unsigned long *devm_bitmap_zalloc(struct device *dev,
1312 unsigned int nbits, gfp_t flags)
1313{
1314 return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
1315}
1316EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
1317
1318#if BITS_PER_LONG == 64
1319
1320
1321
1322
1323
1324
1325void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
1326{
1327 unsigned int i, halfwords;
1328
1329 halfwords = DIV_ROUND_UP(nbits, 32);
1330 for (i = 0; i < halfwords; i++) {
1331 bitmap[i/2] = (unsigned long) buf[i];
1332 if (++i < halfwords)
1333 bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
1334 }
1335
1336
1337 if (nbits % BITS_PER_LONG)
1338 bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
1339}
1340EXPORT_SYMBOL(bitmap_from_arr32);
1341
1342
1343
1344
1345
1346
1347
1348void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
1349{
1350 unsigned int i, halfwords;
1351
1352 halfwords = DIV_ROUND_UP(nbits, 32);
1353 for (i = 0; i < halfwords; i++) {
1354 buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
1355 if (++i < halfwords)
1356 buf[i] = (u32) (bitmap[i/2] >> 32);
1357 }
1358
1359
1360 if (nbits % BITS_PER_LONG)
1361 buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
1362}
1363EXPORT_SYMBOL(bitmap_to_arr32);
1364
1365#endif
1366