511 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2 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 bitmap17 *18 * @ubuf: pointer to user buffer containing string.19 * @ulen: buffer size in bytes. If string is smaller than this20 * 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 */24int 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}40EXPORT_SYMBOL(bitmap_parse_user);41 42/**43 * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string44 * @list: indicates whether the bitmap must be list45 * @buf: page aligned buffer into which string is placed46 * @maskp: pointer to bitmap to convert47 * @nmaskbits: size of bitmap, in bits48 *49 * Output format is a comma-separated list of decimal numbers and50 * ranges if list is specified or hex digits grouped into comma-separated51 * 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-aligned54 * area and that sufficient storage remains at @buf to accommodate the55 * bitmap_print_to_pagebuf() output. Returns the number of characters56 * actually printed to @buf, excluding terminating '\0'.57 */58int 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}66EXPORT_SYMBOL(bitmap_print_to_pagebuf);67 68/**69 * bitmap_print_to_buf - convert bitmap to list or hex format ASCII string70 * @list: indicates whether the bitmap must be list71 * true: print in decimal list format72 * false: print in hexadecimal bitmask format73 * @buf: buffer into which string is placed74 * @maskp: pointer to bitmap to convert75 * @nmaskbits: size of bitmap, in bits76 * @off: in the string from which we are copying, We copy to @buf77 * @count: the maximum number of bytes to print78 */79static 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 string98 * @buf: buffer into which string is placed99 * @maskp: pointer to bitmap to convert100 * @nmaskbits: size of bitmap, in bits101 * @off: in the string from which we are copying, We copy to @buf102 * @count: the maximum number of bytes to print103 *104 * The bitmap_print_to_pagebuf() is used indirectly via its cpumap wrapper105 * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal106 * bitmask and decimal list to userspace by sysfs ABI.107 * Drivers might be using a normal attribute for this kind of ABIs. A108 * 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 this118 * means the file is limited to one page only.119 * bitmap_print_to_pagebuf() API works terribly well for this kind of120 * 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 a128 * bitmask or list more than one page. Especially for list, it could be129 * 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_attribute131 * has show entry as below::132 *133 * static ssize_t134 * 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 able142 * to support file size more than one page. For example, offset could be143 * >= 4096.144 * bitmap_print_bitmask_to_buf(), bitmap_print_list_to_buf() wit their145 * 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 they147 * move to use bin_attribute. In result, we have to pass the corresponding148 * 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 that152 * bitmap_print_to_pagebuf() mainly serves sysfs attribute with the assumption153 * 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 other155 * 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 hexadecimal157 * 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 be163 * 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 correct169 * list representation of bitmap. Particularly, some bits within or out of170 * related interval may be erroneously set or unset. The format of the string171 * 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 order173 * 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 bitmap175 * unchanged between the very first and very last call. Otherwise concatenated176 * result may be incorrect, and format may be broken.177 *178 * Returns the number of characters actually printed to @buf179 */180int 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}185EXPORT_SYMBOL(bitmap_print_bitmask_to_buf);186 187/**188 * bitmap_print_list_to_buf - convert bitmap to decimal list format ASCII string189 * @buf: buffer into which string is placed190 * @maskp: pointer to bitmap to convert191 * @nmaskbits: size of bitmap, in bits192 * @off: in the string from which we are copying, We copy to @buf193 * @count: the maximum number of bytes to print194 *195 * Everything is same with the above bitmap_print_bitmask_to_buf() except196 * the print format.197 */198int 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}203EXPORT_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 N208 * .........****......****......****..................209 * ^ ^ ^ ^ ^210 * start off group_len end nbits211 */212struct region {213 unsigned int start;214 unsigned int off;215 unsigned int group_len;216 unsigned int end;217 unsigned int nbits;218};219 220static 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 228static 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 239static 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 260static inline bool end_of_str(char c)261{262 return c == '\0' || c == '\n';263}264 265static inline bool __end_of_region(char c)266{267 return isspace(c) || c == ',';268}269 270static 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 beginning277 * of the region.278 */279static 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 287static 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 295static 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 321check_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 337no_end:338 r->end = r->start;339no_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 bitmap348 * @buf: read user string from this buffer; must be terminated349 * with a \0 or \n.350 * @maskp: write resulting mask here351 * @nmaskbits: number of bits in mask to be written352 *353 * Input format is a comma-separated list of decimal numbers and354 * ranges. Consecutively set bits are shown as two hyphen-separated355 * decimal numbers, the smallest and largest bit numbers set in356 * the range.357 * Optionally each range can be postfixed to denote that only parts of it358 * 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_size361 * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769362 * The value 'N' can be used as a dynamically substituted token for the363 * maximum allowed value; i.e (nmaskbits - 1). Keep in mind that it is364 * dynamic, so if system changes cause the bitmap width to change, such365 * 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 format370 * - ``-EINVAL``: invalid character in string371 * - ``-ERANGE``: bit number specified too large for mask372 * - ``-EOVERFLOW``: integer overflow in the input parameters373 */374int 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}400EXPORT_SYMBOL(bitmap_parselist);401 402 403/**404 * bitmap_parselist_user() - convert user buffer's list format ASCII405 * string to bitmap406 *407 * @ubuf: pointer to user buffer containing string.408 * @ulen: buffer size in bytes. If string is smaller than this409 * 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 */415int 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}431EXPORT_SYMBOL(bitmap_parselist_user);432 433static 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);452out: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 this461 * 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 32467 * bits of the resultant bitmask. No chunk may specify a value larger468 * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value469 * then leading 0-bits are prepended. %-EINVAL is returned for illegal470 * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.471 * Leading, embedded and trailing whitespace accepted.472 */473int 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#else493 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);494#endif495 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}510EXPORT_SYMBOL(bitmap_parse);511