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
496static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp,
497 int nmaskbits, loff_t off, size_t count)
498{
499 const char *fmt = list ? "%*pbl\n" : "%*pb\n";
500 ssize_t size;
501 void *data;
502
503 data = kasprintf(GFP_KERNEL, fmt, nmaskbits, maskp);
504 if (!data)
505 return -ENOMEM;
506
507 size = memory_read_from_buffer(buf, count, &off, data, strlen(data) + 1);
508 kfree(data);
509
510 return size;
511}
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
592 int nmaskbits, loff_t off, size_t count)
593{
594 return bitmap_print_to_buf(false, buf, maskp, nmaskbits, off, count);
595}
596EXPORT_SYMBOL(bitmap_print_bitmask_to_buf);
597
598
599
600
601
602
603
604int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
605 int nmaskbits, loff_t off, size_t count)
606{
607 return bitmap_print_to_buf(true, buf, maskp, nmaskbits, off, count);
608}
609EXPORT_SYMBOL(bitmap_print_list_to_buf);
610
611
612
613
614
615
616
617
618struct region {
619 unsigned int start;
620 unsigned int off;
621 unsigned int group_len;
622 unsigned int end;
623 unsigned int nbits;
624};
625
626static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
627{
628 unsigned int start;
629
630 for (start = r->start; start <= r->end; start += r->group_len)
631 bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
632}
633
634static int bitmap_check_region(const struct region *r)
635{
636 if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
637 return -EINVAL;
638
639 if (r->end >= r->nbits)
640 return -ERANGE;
641
642 return 0;
643}
644
645static const char *bitmap_getnum(const char *str, unsigned int *num,
646 unsigned int lastbit)
647{
648 unsigned long long n;
649 unsigned int len;
650
651 if (str[0] == 'N') {
652 *num = lastbit;
653 return str + 1;
654 }
655
656 len = _parse_integer(str, 10, &n);
657 if (!len)
658 return ERR_PTR(-EINVAL);
659 if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
660 return ERR_PTR(-EOVERFLOW);
661
662 *num = n;
663 return str + len;
664}
665
666static inline bool end_of_str(char c)
667{
668 return c == '\0' || c == '\n';
669}
670
671static inline bool __end_of_region(char c)
672{
673 return isspace(c) || c == ',';
674}
675
676static inline bool end_of_region(char c)
677{
678 return __end_of_region(c) || end_of_str(c);
679}
680
681
682
683
684
685static const char *bitmap_find_region(const char *str)
686{
687 while (__end_of_region(*str))
688 str++;
689
690 return end_of_str(*str) ? NULL : str;
691}
692
693static const char *bitmap_find_region_reverse(const char *start, const char *end)
694{
695 while (start <= end && __end_of_region(*end))
696 end--;
697
698 return end;
699}
700
701static const char *bitmap_parse_region(const char *str, struct region *r)
702{
703 unsigned int lastbit = r->nbits - 1;
704
705 if (!strncasecmp(str, "all", 3)) {
706 r->start = 0;
707 r->end = lastbit;
708 str += 3;
709
710 goto check_pattern;
711 }
712
713 str = bitmap_getnum(str, &r->start, lastbit);
714 if (IS_ERR(str))
715 return str;
716
717 if (end_of_region(*str))
718 goto no_end;
719
720 if (*str != '-')
721 return ERR_PTR(-EINVAL);
722
723 str = bitmap_getnum(str + 1, &r->end, lastbit);
724 if (IS_ERR(str))
725 return str;
726
727check_pattern:
728 if (end_of_region(*str))
729 goto no_pattern;
730
731 if (*str != ':')
732 return ERR_PTR(-EINVAL);
733
734 str = bitmap_getnum(str + 1, &r->off, lastbit);
735 if (IS_ERR(str))
736 return str;
737
738 if (*str != '/')
739 return ERR_PTR(-EINVAL);
740
741 return bitmap_getnum(str + 1, &r->group_len, lastbit);
742
743no_end:
744 r->end = r->start;
745no_pattern:
746 r->off = r->end + 1;
747 r->group_len = r->end + 1;
748
749 return end_of_str(*str) ? NULL : str;
750}
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
781{
782 struct region r;
783 long ret;
784
785 r.nbits = nmaskbits;
786 bitmap_zero(maskp, r.nbits);
787
788 while (buf) {
789 buf = bitmap_find_region(buf);
790 if (buf == NULL)
791 return 0;
792
793 buf = bitmap_parse_region(buf, &r);
794 if (IS_ERR(buf))
795 return PTR_ERR(buf);
796
797 ret = bitmap_check_region(&r);
798 if (ret)
799 return ret;
800
801 bitmap_set_region(&r, maskp);
802 }
803
804 return 0;
805}
806EXPORT_SYMBOL(bitmap_parselist);
807
808
809
810
811
812
813
814
815
816
817
818
819
820int bitmap_parselist_user(const char __user *ubuf,
821 unsigned int ulen, unsigned long *maskp,
822 int nmaskbits)
823{
824 char *buf;
825 int ret;
826
827 buf = memdup_user_nul(ubuf, ulen);
828 if (IS_ERR(buf))
829 return PTR_ERR(buf);
830
831 ret = bitmap_parselist(buf, maskp, nmaskbits);
832
833 kfree(buf);
834 return ret;
835}
836EXPORT_SYMBOL(bitmap_parselist_user);
837
838static const char *bitmap_get_x32_reverse(const char *start,
839 const char *end, u32 *num)
840{
841 u32 ret = 0;
842 int c, i;
843
844 for (i = 0; i < 32; i += 4) {
845 c = hex_to_bin(*end--);
846 if (c < 0)
847 return ERR_PTR(-EINVAL);
848
849 ret |= c << i;
850
851 if (start > end || __end_of_region(*end))
852 goto out;
853 }
854
855 if (hex_to_bin(*end--) >= 0)
856 return ERR_PTR(-EOVERFLOW);
857out:
858 *num = ret;
859 return end;
860}
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878int bitmap_parse(const char *start, unsigned int buflen,
879 unsigned long *maskp, int nmaskbits)
880{
881 const char *end = strnchrnul(start, buflen, '\n') - 1;
882 int chunks = BITS_TO_U32(nmaskbits);
883 u32 *bitmap = (u32 *)maskp;
884 int unset_bit;
885 int chunk;
886
887 for (chunk = 0; ; chunk++) {
888 end = bitmap_find_region_reverse(start, end);
889 if (start > end)
890 break;
891
892 if (!chunks--)
893 return -EOVERFLOW;
894
895#if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
896 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
897#else
898 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
899#endif
900 if (IS_ERR(end))
901 return PTR_ERR(end);
902 }
903
904 unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
905 if (unset_bit < nmaskbits) {
906 bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
907 return 0;
908 }
909
910 if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
911 return -EOVERFLOW;
912
913 return 0;
914}
915EXPORT_SYMBOL(bitmap_parse);
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
936{
937 if (pos >= nbits || !test_bit(pos, buf))
938 return -1;
939
940 return __bitmap_weight(buf, pos);
941}
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
962{
963 unsigned int pos;
964
965 for (pos = find_first_bit(buf, nbits);
966 pos < nbits && ord;
967 pos = find_next_bit(buf, nbits, pos + 1))
968 ord--;
969
970 return pos;
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
1005void bitmap_remap(unsigned long *dst, const unsigned long *src,
1006 const unsigned long *old, const unsigned long *new,
1007 unsigned int nbits)
1008{
1009 unsigned int oldbit, w;
1010
1011 if (dst == src)
1012 return;
1013 bitmap_zero(dst, nbits);
1014
1015 w = bitmap_weight(new, nbits);
1016 for_each_set_bit(oldbit, src, nbits) {
1017 int n = bitmap_pos_to_ord(old, oldbit, nbits);
1018
1019 if (n < 0 || w == 0)
1020 set_bit(oldbit, dst);
1021 else
1022 set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
1023 }
1024}
1025EXPORT_SYMBOL(bitmap_remap);
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
1051
1052
1053int bitmap_bitremap(int oldbit, const unsigned long *old,
1054 const unsigned long *new, int bits)
1055{
1056 int w = bitmap_weight(new, bits);
1057 int n = bitmap_pos_to_ord(old, oldbit, bits);
1058 if (n < 0 || w == 0)
1059 return oldbit;
1060 else
1061 return bitmap_ord_to_pos(new, n % w, bits);
1062}
1063EXPORT_SYMBOL(bitmap_bitremap);
1064
1065#ifdef CONFIG_NUMA
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172void bitmap_onto(unsigned long *dst, const unsigned long *orig,
1173 const unsigned long *relmap, unsigned int bits)
1174{
1175 unsigned int n, m;
1176
1177 if (dst == orig)
1178 return;
1179 bitmap_zero(dst, bits);
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191 m = 0;
1192 for_each_set_bit(n, relmap, bits) {
1193
1194 if (test_bit(m, orig))
1195 set_bit(n, dst);
1196 m++;
1197 }
1198}
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211void bitmap_fold(unsigned long *dst, const unsigned long *orig,
1212 unsigned int sz, unsigned int nbits)
1213{
1214 unsigned int oldbit;
1215
1216 if (dst == orig)
1217 return;
1218 bitmap_zero(dst, nbits);
1219
1220 for_each_set_bit(oldbit, orig, nbits)
1221 set_bit(oldbit % sz, dst);
1222}
1223#endif
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243enum {
1244 REG_OP_ISFREE,
1245 REG_OP_ALLOC,
1246 REG_OP_RELEASE,
1247};
1248
1249static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1250{
1251 int nbits_reg;
1252 int index;
1253 int offset;
1254 int nlongs_reg;
1255 int nbitsinlong;
1256 unsigned long mask;
1257 int i;
1258 int ret = 0;
1259
1260
1261
1262
1263
1264 nbits_reg = 1 << order;
1265 index = pos / BITS_PER_LONG;
1266 offset = pos - (index * BITS_PER_LONG);
1267 nlongs_reg = BITS_TO_LONGS(nbits_reg);
1268 nbitsinlong = min(nbits_reg, BITS_PER_LONG);
1269
1270
1271
1272
1273
1274 mask = (1UL << (nbitsinlong - 1));
1275 mask += mask - 1;
1276 mask <<= offset;
1277
1278 switch (reg_op) {
1279 case REG_OP_ISFREE:
1280 for (i = 0; i < nlongs_reg; i++) {
1281 if (bitmap[index + i] & mask)
1282 goto done;
1283 }
1284 ret = 1;
1285 break;
1286
1287 case REG_OP_ALLOC:
1288 for (i = 0; i < nlongs_reg; i++)
1289 bitmap[index + i] |= mask;
1290 break;
1291
1292 case REG_OP_RELEASE:
1293 for (i = 0; i < nlongs_reg; i++)
1294 bitmap[index + i] &= ~mask;
1295 break;
1296 }
1297done:
1298 return ret;
1299}
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1316{
1317 unsigned int pos, end;
1318
1319 for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1320 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1321 continue;
1322 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1323 return pos;
1324 }
1325 return -ENOMEM;
1326}
1327EXPORT_SYMBOL(bitmap_find_free_region);
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1341{
1342 __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1343}
1344EXPORT_SYMBOL(bitmap_release_region);
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1358{
1359 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1360 return -EBUSY;
1361 return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1362}
1363EXPORT_SYMBOL(bitmap_allocate_region);
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373#ifdef __BIG_ENDIAN
1374void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
1375{
1376 unsigned int i;
1377
1378 for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1379 if (BITS_PER_LONG == 64)
1380 dst[i] = cpu_to_le64(src[i]);
1381 else
1382 dst[i] = cpu_to_le32(src[i]);
1383 }
1384}
1385EXPORT_SYMBOL(bitmap_copy_le);
1386#endif
1387
1388unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
1389{
1390 return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1391 flags);
1392}
1393EXPORT_SYMBOL(bitmap_alloc);
1394
1395unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
1396{
1397 return bitmap_alloc(nbits, flags | __GFP_ZERO);
1398}
1399EXPORT_SYMBOL(bitmap_zalloc);
1400
1401void bitmap_free(const unsigned long *bitmap)
1402{
1403 kfree(bitmap);
1404}
1405EXPORT_SYMBOL(bitmap_free);
1406
1407static void devm_bitmap_free(void *data)
1408{
1409 unsigned long *bitmap = data;
1410
1411 bitmap_free(bitmap);
1412}
1413
1414unsigned long *devm_bitmap_alloc(struct device *dev,
1415 unsigned int nbits, gfp_t flags)
1416{
1417 unsigned long *bitmap;
1418 int ret;
1419
1420 bitmap = bitmap_alloc(nbits, flags);
1421 if (!bitmap)
1422 return NULL;
1423
1424 ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
1425 if (ret)
1426 return NULL;
1427
1428 return bitmap;
1429}
1430EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
1431
1432unsigned long *devm_bitmap_zalloc(struct device *dev,
1433 unsigned int nbits, gfp_t flags)
1434{
1435 return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
1436}
1437EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
1438
1439#if BITS_PER_LONG == 64
1440
1441
1442
1443
1444
1445
1446void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
1447{
1448 unsigned int i, halfwords;
1449
1450 halfwords = DIV_ROUND_UP(nbits, 32);
1451 for (i = 0; i < halfwords; i++) {
1452 bitmap[i/2] = (unsigned long) buf[i];
1453 if (++i < halfwords)
1454 bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
1455 }
1456
1457
1458 if (nbits % BITS_PER_LONG)
1459 bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
1460}
1461EXPORT_SYMBOL(bitmap_from_arr32);
1462
1463
1464
1465
1466
1467
1468
1469void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
1470{
1471 unsigned int i, halfwords;
1472
1473 halfwords = DIV_ROUND_UP(nbits, 32);
1474 for (i = 0; i < halfwords; i++) {
1475 buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
1476 if (++i < halfwords)
1477 buf[i] = (u32) (bitmap[i/2] >> 32);
1478 }
1479
1480
1481 if (nbits % BITS_PER_LONG)
1482 buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
1483}
1484EXPORT_SYMBOL(bitmap_to_arr32);
1485
1486#endif
1487