lib/bitmap-str.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2
   3 #include <linux/bitmap.h>
   4 #include <linux/ctype.h>
   5 #include <linux/errno.h>
   6 #include <linux/err.h>
   7 #include <linux/export.h>
   8 #include <linux/hex.h>
   9 #include <linux/kernel.h>
  10 #include <linux/mm.h>
  11 #include <linux/string.h>
  12
  13 #include "kstrtox.h"
  14
  15 /**
  16  * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
  17  *
  18  * @ubuf: pointer to user buffer containing string.
  19  * @ulen: buffer size in bytes.  If string is smaller than this
  20  *    then it must be terminated with a \0.
  21  * @maskp: pointer to bitmap array that will contain result.
  22  * @nmaskbits: size of bitmap, in bits.
  23  */
  24 int bitmap_parse_user(const char __user *ubuf,
  25                         unsigned int ulen, unsigned long *maskp,
  26                         int nmaskbits)
  27 {
  28         char *buf;
  29         int ret;
  30
  31         buf = memdup_user_nul(ubuf, ulen);
  32         if (IS_ERR(buf))
  33                 return PTR_ERR(buf);
  34
  35         ret = bitmap_parse(buf, UINT_MAX, maskp, nmaskbits);
  36
  37         kfree(buf);
  38         return ret;
  39 }
  40 EXPORT_SYMBOL(bitmap_parse_user);
  41
  42 /**
  43  * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string
  44  * @list: indicates whether the bitmap must be list
  45  * @buf: page aligned buffer into which string is placed
  46  * @maskp: pointer to bitmap to convert
  47  * @nmaskbits: size of bitmap, in bits
  48  *
  49  * Output format is a comma-separated list of decimal numbers and
  50  * ranges if list is specified or hex digits grouped into comma-separated
  51  * sets of 8 digits/set. Returns the number of characters written to buf.
  52  *
  53  * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
  54  * area and that sufficient storage remains at @buf to accommodate the
  55  * bitmap_print_to_pagebuf() output. Returns the number of characters
  56  * actually printed to @buf, excluding terminating '\0'.
  57  */
  58 int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
  59                             int nmaskbits)
  60 {
  61         ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);
  62
  63         return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
  64                       scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
  65 }
  66 EXPORT_SYMBOL(bitmap_print_to_pagebuf);
  67
  68 /**
  69  * bitmap_print_to_buf  - convert bitmap to list or hex format ASCII string
  70  * @list: indicates whether the bitmap must be list
  71  *      true:  print in decimal list format
  72  *      false: print in hexadecimal bitmask format
  73  * @buf: buffer into which string is placed
  74  * @maskp: pointer to bitmap to convert
  75  * @nmaskbits: size of bitmap, in bits
  76  * @off: in the string from which we are copying, We copy to @buf
  77  * @count: the maximum number of bytes to print
  78  */
  79 static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp,
  80                 int nmaskbits, loff_t off, size_t count)
  81 {
  82         const char *fmt = list ? "%*pbl\n" : "%*pb\n";
  83         ssize_t size;
  84         void *data;
  85
  86         data = kasprintf(GFP_KERNEL, fmt, nmaskbits, maskp);
  87         if (!data)
  88                 return -ENOMEM;
  89
  90         size = memory_read_from_buffer(buf, count, &off, data, strlen(data) + 1);
  91         kfree(data);
  92
  93         return size;
  94 }
  95
  96 /**
  97  * bitmap_print_bitmask_to_buf  - convert bitmap to hex bitmask format ASCII string
  98  * @buf: buffer into which string is placed
  99  * @maskp: pointer to bitmap to convert
 100  * @nmaskbits: size of bitmap, in bits
 101  * @off: in the string from which we are copying, We copy to @buf
 102  * @count: the maximum number of bytes to print
 103  *
 104  * The bitmap_print_to_pagebuf() is used indirectly via its cpumap wrapper
 105  * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal
 106  * bitmask and decimal list to userspace by sysfs ABI.
 107  * Drivers might be using a normal attribute for this kind of ABIs. A
 108  * normal attribute typically has show entry as below::
 109  *
 110  *   static ssize_t example_attribute_show(struct device *dev,
 111  *              struct device_attribute *attr, char *buf)
 112  *   {
 113  *      ...
 114  *      return bitmap_print_to_pagebuf(true, buf, &mask, nr_trig_max);
 115  *   }
 116  *
 117  * show entry of attribute has no offset and count parameters and this
 118  * means the file is limited to one page only.
 119  * bitmap_print_to_pagebuf() API works terribly well for this kind of
 120  * normal attribute with buf parameter and without offset, count::
 121  *
 122  *   bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
 123  *                         int nmaskbits)
 124  *   {
 125  *   }
 126  *
 127  * The problem is once we have a large bitmap, we have a chance to get a
 128  * bitmask or list more than one page. Especially for list, it could be
 129  * as complex as 0,3,5,7,9,... We have no simple way to know it exact size.
 130  * It turns out bin_attribute is a way to break this limit. bin_attribute
 131  * has show entry as below::
 132  *
 133  *   static ssize_t
 134  *   example_bin_attribute_show(struct file *filp, struct kobject *kobj,
 135  *              struct bin_attribute *attr, char *buf,
 136  *              loff_t offset, size_t count)
 137  *   {
 138  *      ...
 139  *   }
 140  *
 141  * With the new offset and count parameters, this makes sysfs ABI be able
 142  * to support file size more than one page. For example, offset could be
 143  * >= 4096.
 144  * bitmap_print_bitmask_to_buf(), bitmap_print_list_to_buf() wit their
 145  * cpumap wrapper cpumap_print_bitmask_to_buf(), cpumap_print_list_to_buf()
 146  * make those drivers be able to support large bitmask and list after they
 147  * move to use bin_attribute. In result, we have to pass the corresponding
 148  * parameters such as off, count from bin_attribute show entry to this API.
 149  *
 150  * The role of cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf()
 151  * is similar with cpumap_print_to_pagebuf(),  the difference is that
 152  * bitmap_print_to_pagebuf() mainly serves sysfs attribute with the assumption
 153  * the destination buffer is exactly one page and won't be more than one page.
 154  * cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf(), on the other
 155  * hand, mainly serves bin_attribute which doesn't work with exact one page,
 156  * and it can break the size limit of converted decimal list and hexadecimal
 157  * bitmask.
 158  *
 159  * WARNING!
 160  *
 161  * This function is not a replacement for sprintf() or bitmap_print_to_pagebuf().
 162  * It is intended to workaround sysfs limitations discussed above and should be
 163  * used carefully in general case for the following reasons:
 164  *
 165  *  - Time complexity is O(nbits^2/count), comparing to O(nbits) for snprintf().
 166  *  - Memory complexity is O(nbits), comparing to O(1) for snprintf().
 167  *  - @off and @count are NOT offset and number of bits to print.
 168  *  - If printing part of bitmap as list, the resulting string is not a correct
 169  *    list representation of bitmap. Particularly, some bits within or out of
 170  *    related interval may be erroneously set or unset. The format of the string
 171  *    may be broken, so bitmap_parselist-like parser may fail parsing it.
 172  *  - If printing the whole bitmap as list by parts, user must ensure the order
 173  *    of calls of the function such that the offset is incremented linearly.
 174  *  - If printing the whole bitmap as list by parts, user must keep bitmap
 175  *    unchanged between the very first and very last call. Otherwise concatenated
 176  *    result may be incorrect, and format may be broken.
 177  *
 178  * Returns the number of characters actually printed to @buf
 179  */
 180 int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
 181                                 int nmaskbits, loff_t off, size_t count)
 182 {
 183         return bitmap_print_to_buf(false, buf, maskp, nmaskbits, off, count);
 184 }
 185 EXPORT_SYMBOL(bitmap_print_bitmask_to_buf);
 186
 187 /**
 188  * bitmap_print_list_to_buf  - convert bitmap to decimal list format ASCII string
 189  * @buf: buffer into which string is placed
 190  * @maskp: pointer to bitmap to convert
 191  * @nmaskbits: size of bitmap, in bits
 192  * @off: in the string from which we are copying, We copy to @buf
 193  * @count: the maximum number of bytes to print
 194  *
 195  * Everything is same with the above bitmap_print_bitmask_to_buf() except
 196  * the print format.
 197  */
 198 int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
 199                              int nmaskbits, loff_t off, size_t count)
 200 {
 201         return bitmap_print_to_buf(true, buf, maskp, nmaskbits, off, count);
 202 }
 203 EXPORT_SYMBOL(bitmap_print_list_to_buf);
 204
 205 /*
 206  * Region 9-38:4/10 describes the following bitmap structure:
 207  * 0       9  12    18                  38           N
 208  * .........****......****......****..................
 209  *          ^  ^     ^                   ^           ^
 210  *      start  off   group_len         end       nbits
 211  */
 212 struct region {
 213         unsigned int start;
 214         unsigned int off;
 215         unsigned int group_len;
 216         unsigned int end;
 217         unsigned int nbits;
 218 };
 219
 220 static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
 221 {
 222         unsigned int start;
 223
 224         for (start = r->start; start <= r->end; start += r->group_len)
 225                 bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
 226 }
 227
 228 static int bitmap_check_region(const struct region *r)
 229 {
 230         if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
 231                 return -EINVAL;
 232
 233         if (r->end >= r->nbits)
 234                 return -ERANGE;
 235
 236         return 0;
 237 }
 238
 239 static const char *bitmap_getnum(const char *str, unsigned int *num,
 240                                  unsigned int lastbit)
 241 {
 242         unsigned long long n;
 243         unsigned int len;
 244
 245         if (str[0] == 'N') {
 246                 *num = lastbit;
 247                 return str + 1;
 248         }
 249
 250         len = _parse_integer(str, 10, &n);
 251         if (!len)
 252                 return ERR_PTR(-EINVAL);
 253         if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
 254                 return ERR_PTR(-EOVERFLOW);
 255
 256         *num = n;
 257         return str + len;
 258 }
 259
 260 static inline bool end_of_str(char c)
 261 {
 262         return c == '\0' || c == '\n';
 263 }
 264
 265 static inline bool __end_of_region(char c)
 266 {
 267         return isspace(c) || c == ',';
 268 }
 269
 270 static inline bool end_of_region(char c)
 271 {
 272         return __end_of_region(c) || end_of_str(c);
 273 }
 274
 275 /*
 276  * The format allows commas and whitespaces at the beginning
 277  * of the region.
 278  */
 279 static const char *bitmap_find_region(const char *str)
 280 {
 281         while (__end_of_region(*str))
 282                 str++;
 283
 284         return end_of_str(*str) ? NULL : str;
 285 }
 286
 287 static const char *bitmap_find_region_reverse(const char *start, const char *end)
 288 {
 289         while (start <= end && __end_of_region(*end))
 290                 end--;
 291
 292         return end;
 293 }
 294
 295 static const char *bitmap_parse_region(const char *str, struct region *r)
 296 {
 297         unsigned int lastbit = r->nbits - 1;
 298
 299         if (!strncasecmp(str, "all", 3)) {
 300                 r->start = 0;
 301                 r->end = lastbit;
 302                 str += 3;
 303
 304                 goto check_pattern;
 305         }
 306
 307         str = bitmap_getnum(str, &r->start, lastbit);
 308         if (IS_ERR(str))
 309                 return str;
 310
 311         if (end_of_region(*str))
 312                 goto no_end;
 313
 314         if (*str != '-')
 315                 return ERR_PTR(-EINVAL);
 316
 317         str = bitmap_getnum(str + 1, &r->end, lastbit);
 318         if (IS_ERR(str))
 319                 return str;
 320
 321 check_pattern:
 322         if (end_of_region(*str))
 323                 goto no_pattern;
 324
 325         if (*str != ':')
 326                 return ERR_PTR(-EINVAL);
 327
 328         str = bitmap_getnum(str + 1, &r->off, lastbit);
 329         if (IS_ERR(str))
 330                 return str;
 331
 332         if (*str != '/')
 333                 return ERR_PTR(-EINVAL);
 334
 335         return bitmap_getnum(str + 1, &r->group_len, lastbit);
 336
 337 no_end:
 338         r->end = r->start;
 339 no_pattern:
 340         r->off = r->end + 1;
 341         r->group_len = r->end + 1;
 342
 343         return end_of_str(*str) ? NULL : str;
 344 }
 345
 346 /**
 347  * bitmap_parselist - convert list format ASCII string to bitmap
 348  * @buf: read user string from this buffer; must be terminated
 349  *    with a \0 or \n.
 350  * @maskp: write resulting mask here
 351  * @nmaskbits: number of bits in mask to be written
 352  *
 353  * Input format is a comma-separated list of decimal numbers and
 354  * ranges.  Consecutively set bits are shown as two hyphen-separated
 355  * decimal numbers, the smallest and largest bit numbers set in
 356  * the range.
 357  * Optionally each range can be postfixed to denote that only parts of it
 358  * should be set. The range will divided to groups of specific size.
 359  * From each group will be used only defined amount of bits.
 360  * Syntax: range:used_size/group_size
 361  * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
 362  * The value 'N' can be used as a dynamically substituted token for the
 363  * maximum allowed value; i.e (nmaskbits - 1).  Keep in mind that it is
 364  * dynamic, so if system changes cause the bitmap width to change, such
 365  * as more cores in a CPU list, then any ranges using N will also change.
 366  *
 367  * Returns: 0 on success, -errno on invalid input strings. Error values:
 368  *
 369  *   - ``-EINVAL``: wrong region format
 370  *   - ``-EINVAL``: invalid character in string
 371  *   - ``-ERANGE``: bit number specified too large for mask
 372  *   - ``-EOVERFLOW``: integer overflow in the input parameters
 373  */
 374 int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
 375 {
 376         struct region r;
 377         long ret;
 378
 379         r.nbits = nmaskbits;
 380         bitmap_zero(maskp, r.nbits);
 381
 382         while (buf) {
 383                 buf = bitmap_find_region(buf);
 384                 if (buf == NULL)
 385                         return 0;
 386
 387                 buf = bitmap_parse_region(buf, &r);
 388                 if (IS_ERR(buf))
 389                         return PTR_ERR(buf);
 390
 391                 ret = bitmap_check_region(&r);
 392                 if (ret)
 393                         return ret;
 394
 395                 bitmap_set_region(&r, maskp);
 396         }
 397
 398         return 0;
 399 }
 400 EXPORT_SYMBOL(bitmap_parselist);
 401
 402
 403 /**
 404  * bitmap_parselist_user() - convert user buffer's list format ASCII
 405  * string to bitmap
 406  *
 407  * @ubuf: pointer to user buffer containing string.
 408  * @ulen: buffer size in bytes.  If string is smaller than this
 409  *    then it must be terminated with a \0.
 410  * @maskp: pointer to bitmap array that will contain result.
 411  * @nmaskbits: size of bitmap, in bits.
 412  *
 413  * Wrapper for bitmap_parselist(), providing it with user buffer.
 414  */
 415 int bitmap_parselist_user(const char __user *ubuf,
 416                         unsigned int ulen, unsigned long *maskp,
 417                         int nmaskbits)
 418 {
 419         char *buf;
 420         int ret;
 421
 422         buf = memdup_user_nul(ubuf, ulen);
 423         if (IS_ERR(buf))
 424                 return PTR_ERR(buf);
 425
 426         ret = bitmap_parselist(buf, maskp, nmaskbits);
 427
 428         kfree(buf);
 429         return ret;
 430 }
 431 EXPORT_SYMBOL(bitmap_parselist_user);
 432
 433 static const char *bitmap_get_x32_reverse(const char *start,
 434                                         const char *end, u32 *num)
 435 {
 436         u32 ret = 0;
 437         int c, i;
 438
 439         for (i = 0; i < 32; i += 4) {
 440                 c = hex_to_bin(*end--);
 441                 if (c < 0)
 442                         return ERR_PTR(-EINVAL);
 443
 444                 ret |= c << i;
 445
 446                 if (start > end || __end_of_region(*end))
 447                         goto out;
 448         }
 449
 450         if (hex_to_bin(*end--) >= 0)
 451                 return ERR_PTR(-EOVERFLOW);
 452 out:
 453         *num = ret;
 454         return end;
 455 }
 456
 457 /**
 458  * bitmap_parse - convert an ASCII hex string into a bitmap.
 459  * @start: pointer to buffer containing string.
 460  * @buflen: buffer size in bytes.  If string is smaller than this
 461  *    then it must be terminated with a \0 or \n. In that case,
 462  *    UINT_MAX may be provided instead of string length.
 463  * @maskp: pointer to bitmap array that will contain result.
 464  * @nmaskbits: size of bitmap, in bits.
 465  *
 466  * Commas group hex digits into chunks.  Each chunk defines exactly 32
 467  * bits of the resultant bitmask.  No chunk may specify a value larger
 468  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
 469  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
 470  * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
 471  * Leading, embedded and trailing whitespace accepted.
 472  */
 473 int bitmap_parse(const char *start, unsigned int buflen,
 474                 unsigned long *maskp, int nmaskbits)
 475 {
 476         const char *end = strnchrnul(start, buflen, '\n') - 1;
 477         int chunks = BITS_TO_U32(nmaskbits);
 478         u32 *bitmap = (u32 *)maskp;
 479         int unset_bit;
 480         int chunk;
 481
 482         for (chunk = 0; ; chunk++) {
 483                 end = bitmap_find_region_reverse(start, end);
 484                 if (start > end)
 485                         break;
 486
 487                 if (!chunks--)
 488                         return -EOVERFLOW;
 489
 490 #if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
 491                 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
 492 #else
 493                 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
 494 #endif
 495                 if (IS_ERR(end))
 496                         return PTR_ERR(end);
 497         }
 498
 499         unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
 500         if (unset_bit < nmaskbits) {
 501                 bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
 502                 return 0;
 503         }
 504
 505         if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
 506                 return -EOVERFLOW;
 507
 508         return 0;
 509 }
 510 EXPORT_SYMBOL(bitmap_parse);