bitmap.c (7733aa893847f021c674d0d30b723d892109369d) bitmap.c (aae06fc1b5a2e4b52f8504a1f12f9b8b98e80641)
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * lib/bitmap.c
4 * Helper functions for bitmap.h.
5 */
6
7#include <linux/bitmap.h>
8#include <linux/bitops.h>
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * lib/bitmap.c
4 * Helper functions for bitmap.h.
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>
9#include <linux/ctype.h>
10#include <linux/device.h>
11#include <linux/errno.h>
12#include <linux/export.h>
14#include <linux/kernel.h>
15#include <linux/mm.h>
16#include <linux/slab.h>
13#include <linux/slab.h>
17#include <linux/string.h>
18#include <linux/thread_info.h>
19#include <linux/uaccess.h>
20
14
21#include <asm/page.h>
22
23#include "kstrtox.h"
24
25/**
26 * DOC: bitmap introduction
27 *
28 * bitmaps provide an array of bits, implemented using an
29 * array of unsigned longs. The number of valid bits in a
30 * given bitmap does _not_ need to be an exact multiple of
31 * BITS_PER_LONG.
32 *

--- 402 unchanged lines hidden (view full) ---

435 if (i < end) {
436 start = i + 1;
437 goto again;
438 }
439 return index;
440}
441EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
442
15/**
16 * DOC: bitmap introduction
17 *
18 * bitmaps provide an array of bits, implemented using 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 *

--- 402 unchanged lines hidden (view full) ---

425 if (i < end) {
426 start = i + 1;
427 goto again;
428 }
429 return index;
430}
431EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
432
443/*
444 * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
445 * second version by Paul Jackson, third by Joe Korty.
446 */
447
448/**
433/**
449 * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
450 *
451 * @ubuf: pointer to user buffer containing string.
452 * @ulen: buffer size in bytes. If string is smaller than this
453 * then it must be terminated with a \0.
454 * @maskp: pointer to bitmap array that will contain result.
455 * @nmaskbits: size of bitmap, in bits.
456 */
457int bitmap_parse_user(const char __user *ubuf,
458 unsigned int ulen, unsigned long *maskp,
459 int nmaskbits)
460{
461 char *buf;
462 int ret;
463
464 buf = memdup_user_nul(ubuf, ulen);
465 if (IS_ERR(buf))
466 return PTR_ERR(buf);
467
468 ret = bitmap_parse(buf, UINT_MAX, maskp, nmaskbits);
469
470 kfree(buf);
471 return ret;
472}
473EXPORT_SYMBOL(bitmap_parse_user);
474
475/**
476 * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string
477 * @list: indicates whether the bitmap must be list
478 * @buf: page aligned buffer into which string is placed
479 * @maskp: pointer to bitmap to convert
480 * @nmaskbits: size of bitmap, in bits
481 *
482 * Output format is a comma-separated list of decimal numbers and
483 * ranges if list is specified or hex digits grouped into comma-separated
484 * sets of 8 digits/set. Returns the number of characters written to buf.
485 *
486 * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
487 * area and that sufficient storage remains at @buf to accommodate the
488 * bitmap_print_to_pagebuf() output. Returns the number of characters
489 * actually printed to @buf, excluding terminating '\0'.
490 */
491int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
492 int nmaskbits)
493{
494 ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);
495
496 return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
497 scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
498}
499EXPORT_SYMBOL(bitmap_print_to_pagebuf);
500
501/**
502 * bitmap_print_to_buf - convert bitmap to list or hex format ASCII string
503 * @list: indicates whether the bitmap must be list
504 * true: print in decimal list format
505 * false: print in hexadecimal bitmask format
506 * @buf: buffer into which string is placed
507 * @maskp: pointer to bitmap to convert
508 * @nmaskbits: size of bitmap, in bits
509 * @off: in the string from which we are copying, We copy to @buf
510 * @count: the maximum number of bytes to print
511 */
512static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp,
513 int nmaskbits, loff_t off, size_t count)
514{
515 const char *fmt = list ? "%*pbl\n" : "%*pb\n";
516 ssize_t size;
517 void *data;
518
519 data = kasprintf(GFP_KERNEL, fmt, nmaskbits, maskp);
520 if (!data)
521 return -ENOMEM;
522
523 size = memory_read_from_buffer(buf, count, &off, data, strlen(data) + 1);
524 kfree(data);
525
526 return size;
527}
528
529/**
530 * bitmap_print_bitmask_to_buf - convert bitmap to hex bitmask format ASCII string
531 * @buf: buffer into which string is placed
532 * @maskp: pointer to bitmap to convert
533 * @nmaskbits: size of bitmap, in bits
534 * @off: in the string from which we are copying, We copy to @buf
535 * @count: the maximum number of bytes to print
536 *
537 * The bitmap_print_to_pagebuf() is used indirectly via its cpumap wrapper
538 * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal
539 * bitmask and decimal list to userspace by sysfs ABI.
540 * Drivers might be using a normal attribute for this kind of ABIs. A
541 * normal attribute typically has show entry as below::
542 *
543 * static ssize_t example_attribute_show(struct device *dev,
544 * struct device_attribute *attr, char *buf)
545 * {
546 * ...
547 * return bitmap_print_to_pagebuf(true, buf, &mask, nr_trig_max);
548 * }
549 *
550 * show entry of attribute has no offset and count parameters and this
551 * means the file is limited to one page only.
552 * bitmap_print_to_pagebuf() API works terribly well for this kind of
553 * normal attribute with buf parameter and without offset, count::
554 *
555 * bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
556 * int nmaskbits)
557 * {
558 * }
559 *
560 * The problem is once we have a large bitmap, we have a chance to get a
561 * bitmask or list more than one page. Especially for list, it could be
562 * as complex as 0,3,5,7,9,... We have no simple way to know it exact size.
563 * It turns out bin_attribute is a way to break this limit. bin_attribute
564 * has show entry as below::
565 *
566 * static ssize_t
567 * example_bin_attribute_show(struct file *filp, struct kobject *kobj,
568 * struct bin_attribute *attr, char *buf,
569 * loff_t offset, size_t count)
570 * {
571 * ...
572 * }
573 *
574 * With the new offset and count parameters, this makes sysfs ABI be able
575 * to support file size more than one page. For example, offset could be
576 * >= 4096.
577 * bitmap_print_bitmask_to_buf(), bitmap_print_list_to_buf() wit their
578 * cpumap wrapper cpumap_print_bitmask_to_buf(), cpumap_print_list_to_buf()
579 * make those drivers be able to support large bitmask and list after they
580 * move to use bin_attribute. In result, we have to pass the corresponding
581 * parameters such as off, count from bin_attribute show entry to this API.
582 *
583 * The role of cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf()
584 * is similar with cpumap_print_to_pagebuf(), the difference is that
585 * bitmap_print_to_pagebuf() mainly serves sysfs attribute with the assumption
586 * the destination buffer is exactly one page and won't be more than one page.
587 * cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf(), on the other
588 * hand, mainly serves bin_attribute which doesn't work with exact one page,
589 * and it can break the size limit of converted decimal list and hexadecimal
590 * bitmask.
591 *
592 * WARNING!
593 *
594 * This function is not a replacement for sprintf() or bitmap_print_to_pagebuf().
595 * It is intended to workaround sysfs limitations discussed above and should be
596 * used carefully in general case for the following reasons:
597 *
598 * - Time complexity is O(nbits^2/count), comparing to O(nbits) for snprintf().
599 * - Memory complexity is O(nbits), comparing to O(1) for snprintf().
600 * - @off and @count are NOT offset and number of bits to print.
601 * - If printing part of bitmap as list, the resulting string is not a correct
602 * list representation of bitmap. Particularly, some bits within or out of
603 * related interval may be erroneously set or unset. The format of the string
604 * may be broken, so bitmap_parselist-like parser may fail parsing it.
605 * - If printing the whole bitmap as list by parts, user must ensure the order
606 * of calls of the function such that the offset is incremented linearly.
607 * - If printing the whole bitmap as list by parts, user must keep bitmap
608 * unchanged between the very first and very last call. Otherwise concatenated
609 * result may be incorrect, and format may be broken.
610 *
611 * Returns the number of characters actually printed to @buf
612 */
613int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
614 int nmaskbits, loff_t off, size_t count)
615{
616 return bitmap_print_to_buf(false, buf, maskp, nmaskbits, off, count);
617}
618EXPORT_SYMBOL(bitmap_print_bitmask_to_buf);
619
620/**
621 * bitmap_print_list_to_buf - convert bitmap to decimal list format ASCII string
622 * @buf: buffer into which string is placed
623 * @maskp: pointer to bitmap to convert
624 * @nmaskbits: size of bitmap, in bits
625 * @off: in the string from which we are copying, We copy to @buf
626 * @count: the maximum number of bytes to print
627 *
628 * Everything is same with the above bitmap_print_bitmask_to_buf() except
629 * the print format.
630 */
631int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
632 int nmaskbits, loff_t off, size_t count)
633{
634 return bitmap_print_to_buf(true, buf, maskp, nmaskbits, off, count);
635}
636EXPORT_SYMBOL(bitmap_print_list_to_buf);
637
638/*
639 * Region 9-38:4/10 describes the following bitmap structure:
640 * 0 9 12 18 38 N
641 * .........****......****......****..................
642 * ^ ^ ^ ^ ^
643 * start off group_len end nbits
644 */
645struct region {
646 unsigned int start;
647 unsigned int off;
648 unsigned int group_len;
649 unsigned int end;
650 unsigned int nbits;
651};
652
653static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
654{
655 unsigned int start;
656
657 for (start = r->start; start <= r->end; start += r->group_len)
658 bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
659}
660
661static int bitmap_check_region(const struct region *r)
662{
663 if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
664 return -EINVAL;
665
666 if (r->end >= r->nbits)
667 return -ERANGE;
668
669 return 0;
670}
671
672static const char *bitmap_getnum(const char *str, unsigned int *num,
673 unsigned int lastbit)
674{
675 unsigned long long n;
676 unsigned int len;
677
678 if (str[0] == 'N') {
679 *num = lastbit;
680 return str + 1;
681 }
682
683 len = _parse_integer(str, 10, &n);
684 if (!len)
685 return ERR_PTR(-EINVAL);
686 if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
687 return ERR_PTR(-EOVERFLOW);
688
689 *num = n;
690 return str + len;
691}
692
693static inline bool end_of_str(char c)
694{
695 return c == '\0' || c == '\n';
696}
697
698static inline bool __end_of_region(char c)
699{
700 return isspace(c) || c == ',';
701}
702
703static inline bool end_of_region(char c)
704{
705 return __end_of_region(c) || end_of_str(c);
706}
707
708/*
709 * The format allows commas and whitespaces at the beginning
710 * of the region.
711 */
712static const char *bitmap_find_region(const char *str)
713{
714 while (__end_of_region(*str))
715 str++;
716
717 return end_of_str(*str) ? NULL : str;
718}
719
720static const char *bitmap_find_region_reverse(const char *start, const char *end)
721{
722 while (start <= end && __end_of_region(*end))
723 end--;
724
725 return end;
726}
727
728static const char *bitmap_parse_region(const char *str, struct region *r)
729{
730 unsigned int lastbit = r->nbits - 1;
731
732 if (!strncasecmp(str, "all", 3)) {
733 r->start = 0;
734 r->end = lastbit;
735 str += 3;
736
737 goto check_pattern;
738 }
739
740 str = bitmap_getnum(str, &r->start, lastbit);
741 if (IS_ERR(str))
742 return str;
743
744 if (end_of_region(*str))
745 goto no_end;
746
747 if (*str != '-')
748 return ERR_PTR(-EINVAL);
749
750 str = bitmap_getnum(str + 1, &r->end, lastbit);
751 if (IS_ERR(str))
752 return str;
753
754check_pattern:
755 if (end_of_region(*str))
756 goto no_pattern;
757
758 if (*str != ':')
759 return ERR_PTR(-EINVAL);
760
761 str = bitmap_getnum(str + 1, &r->off, lastbit);
762 if (IS_ERR(str))
763 return str;
764
765 if (*str != '/')
766 return ERR_PTR(-EINVAL);
767
768 return bitmap_getnum(str + 1, &r->group_len, lastbit);
769
770no_end:
771 r->end = r->start;
772no_pattern:
773 r->off = r->end + 1;
774 r->group_len = r->end + 1;
775
776 return end_of_str(*str) ? NULL : str;
777}
778
779/**
780 * bitmap_parselist - convert list format ASCII string to bitmap
781 * @buf: read user string from this buffer; must be terminated
782 * with a \0 or \n.
783 * @maskp: write resulting mask here
784 * @nmaskbits: number of bits in mask to be written
785 *
786 * Input format is a comma-separated list of decimal numbers and
787 * ranges. Consecutively set bits are shown as two hyphen-separated
788 * decimal numbers, the smallest and largest bit numbers set in
789 * the range.
790 * Optionally each range can be postfixed to denote that only parts of it
791 * should be set. The range will divided to groups of specific size.
792 * From each group will be used only defined amount of bits.
793 * Syntax: range:used_size/group_size
794 * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
795 * The value 'N' can be used as a dynamically substituted token for the
796 * maximum allowed value; i.e (nmaskbits - 1). Keep in mind that it is
797 * dynamic, so if system changes cause the bitmap width to change, such
798 * as more cores in a CPU list, then any ranges using N will also change.
799 *
800 * Returns: 0 on success, -errno on invalid input strings. Error values:
801 *
802 * - ``-EINVAL``: wrong region format
803 * - ``-EINVAL``: invalid character in string
804 * - ``-ERANGE``: bit number specified too large for mask
805 * - ``-EOVERFLOW``: integer overflow in the input parameters
806 */
807int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
808{
809 struct region r;
810 long ret;
811
812 r.nbits = nmaskbits;
813 bitmap_zero(maskp, r.nbits);
814
815 while (buf) {
816 buf = bitmap_find_region(buf);
817 if (buf == NULL)
818 return 0;
819
820 buf = bitmap_parse_region(buf, &r);
821 if (IS_ERR(buf))
822 return PTR_ERR(buf);
823
824 ret = bitmap_check_region(&r);
825 if (ret)
826 return ret;
827
828 bitmap_set_region(&r, maskp);
829 }
830
831 return 0;
832}
833EXPORT_SYMBOL(bitmap_parselist);
834
835
836/**
837 * bitmap_parselist_user() - convert user buffer's list format ASCII
838 * string to bitmap
839 *
840 * @ubuf: pointer to user buffer containing string.
841 * @ulen: buffer size in bytes. If string is smaller than this
842 * then it must be terminated with a \0.
843 * @maskp: pointer to bitmap array that will contain result.
844 * @nmaskbits: size of bitmap, in bits.
845 *
846 * Wrapper for bitmap_parselist(), providing it with user buffer.
847 */
848int bitmap_parselist_user(const char __user *ubuf,
849 unsigned int ulen, unsigned long *maskp,
850 int nmaskbits)
851{
852 char *buf;
853 int ret;
854
855 buf = memdup_user_nul(ubuf, ulen);
856 if (IS_ERR(buf))
857 return PTR_ERR(buf);
858
859 ret = bitmap_parselist(buf, maskp, nmaskbits);
860
861 kfree(buf);
862 return ret;
863}
864EXPORT_SYMBOL(bitmap_parselist_user);
865
866static const char *bitmap_get_x32_reverse(const char *start,
867 const char *end, u32 *num)
868{
869 u32 ret = 0;
870 int c, i;
871
872 for (i = 0; i < 32; i += 4) {
873 c = hex_to_bin(*end--);
874 if (c < 0)
875 return ERR_PTR(-EINVAL);
876
877 ret |= c << i;
878
879 if (start > end || __end_of_region(*end))
880 goto out;
881 }
882
883 if (hex_to_bin(*end--) >= 0)
884 return ERR_PTR(-EOVERFLOW);
885out:
886 *num = ret;
887 return end;
888}
889
890/**
891 * bitmap_parse - convert an ASCII hex string into a bitmap.
892 * @start: pointer to buffer containing string.
893 * @buflen: buffer size in bytes. If string is smaller than this
894 * then it must be terminated with a \0 or \n. In that case,
895 * UINT_MAX may be provided instead of string length.
896 * @maskp: pointer to bitmap array that will contain result.
897 * @nmaskbits: size of bitmap, in bits.
898 *
899 * Commas group hex digits into chunks. Each chunk defines exactly 32
900 * bits of the resultant bitmask. No chunk may specify a value larger
901 * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
902 * then leading 0-bits are prepended. %-EINVAL is returned for illegal
903 * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
904 * Leading, embedded and trailing whitespace accepted.
905 */
906int bitmap_parse(const char *start, unsigned int buflen,
907 unsigned long *maskp, int nmaskbits)
908{
909 const char *end = strnchrnul(start, buflen, '\n') - 1;
910 int chunks = BITS_TO_U32(nmaskbits);
911 u32 *bitmap = (u32 *)maskp;
912 int unset_bit;
913 int chunk;
914
915 for (chunk = 0; ; chunk++) {
916 end = bitmap_find_region_reverse(start, end);
917 if (start > end)
918 break;
919
920 if (!chunks--)
921 return -EOVERFLOW;
922
923#if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
924 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
925#else
926 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
927#endif
928 if (IS_ERR(end))
929 return PTR_ERR(end);
930 }
931
932 unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
933 if (unset_bit < nmaskbits) {
934 bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
935 return 0;
936 }
937
938 if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
939 return -EOVERFLOW;
940
941 return 0;
942}
943EXPORT_SYMBOL(bitmap_parse);
944
945/**
946 * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
947 * @buf: pointer to a bitmap
948 * @pos: a bit position in @buf (0 <= @pos < @nbits)
949 * @nbits: number of valid bit positions in @buf
950 *
951 * Map the bit at position @pos in @buf (of length @nbits) to the
952 * ordinal of which set bit it is. If it is not set or if @pos
953 * is not a valid bit position, map to -1.

--- 575 unchanged lines hidden --- 		434 * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
435 * @buf: pointer to a bitmap
436 * @pos: a bit position in @buf (0 <= @pos < @nbits)
437 * @nbits: number of valid bit positions in @buf
438 *
439 * Map the bit at position @pos in @buf (of length @nbits) to the
440 * ordinal of which set bit it is. If it is not set or if @pos
441 * is not a valid bit position, map to -1.

--- 575 unchanged lines hidden ---