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 */ 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 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 */ 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 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 */ 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 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 */ 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 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 */ 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 N 208 * .........****......****......****.................. 209 * ^ ^ ^ ^ ^ 210 * start off group_len end nbits 211 */ 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 beginning 277 * 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 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 */ 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 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 */ 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 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 */ 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#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} 510EXPORT_SYMBOL(bitmap_parse); 511