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(ptr: buf)) |
33 | return PTR_ERR(ptr: buf); |
34 | |
35 | ret = bitmap_parse(buf, UINT_MAX, dst: maskp, nbits: nmaskbits); |
36 | |
37 | kfree(objp: 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, size: len, fmt: "%*pbl\n" , nmaskbits, maskp) : |
64 | scnprintf(buf, size: len, fmt: "%*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(to: buf, count, ppos: &off, from: data, strlen(data) + 1); |
91 | kfree(objp: 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(list: 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(list: 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(map: 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(s: str, base: 10, res: &n); |
251 | if (!len) |
252 | return ERR_PTR(error: -EINVAL); |
253 | if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n) |
254 | return ERR_PTR(error: -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(c: *str)) |
282 | str++; |
283 | |
284 | return end_of_str(c: *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(c: *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(s1: str, s2: "all" , n: 3)) { |
300 | r->start = 0; |
301 | r->end = lastbit; |
302 | str += 3; |
303 | |
304 | goto check_pattern; |
305 | } |
306 | |
307 | str = bitmap_getnum(str, num: &r->start, lastbit); |
308 | if (IS_ERR(ptr: str)) |
309 | return str; |
310 | |
311 | if (end_of_region(c: *str)) |
312 | goto no_end; |
313 | |
314 | if (*str != '-') |
315 | return ERR_PTR(error: -EINVAL); |
316 | |
317 | str = bitmap_getnum(str: str + 1, num: &r->end, lastbit); |
318 | if (IS_ERR(ptr: str)) |
319 | return str; |
320 | |
321 | check_pattern: |
322 | if (end_of_region(c: *str)) |
323 | goto no_pattern; |
324 | |
325 | if (*str != ':') |
326 | return ERR_PTR(error: -EINVAL); |
327 | |
328 | str = bitmap_getnum(str: str + 1, num: &r->off, lastbit); |
329 | if (IS_ERR(ptr: str)) |
330 | return str; |
331 | |
332 | if (*str != '/') |
333 | return ERR_PTR(error: -EINVAL); |
334 | |
335 | return bitmap_getnum(str: str + 1, num: &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(c: *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(dst: maskp, nbits: r.nbits); |
381 | |
382 | while (buf) { |
383 | buf = bitmap_find_region(str: buf); |
384 | if (buf == NULL) |
385 | return 0; |
386 | |
387 | buf = bitmap_parse_region(str: buf, r: &r); |
388 | if (IS_ERR(ptr: buf)) |
389 | return PTR_ERR(ptr: buf); |
390 | |
391 | ret = bitmap_check_region(r: &r); |
392 | if (ret) |
393 | return ret; |
394 | |
395 | bitmap_set_region(r: &r, bitmap: 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(ptr: buf)) |
424 | return PTR_ERR(ptr: buf); |
425 | |
426 | ret = bitmap_parselist(buf, maskp, nmaskbits); |
427 | |
428 | kfree(objp: 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(ch: *end--); |
441 | if (c < 0) |
442 | return ERR_PTR(error: -EINVAL); |
443 | |
444 | ret |= c << i; |
445 | |
446 | if (start > end || __end_of_region(c: *end)) |
447 | goto out; |
448 | } |
449 | |
450 | if (hex_to_bin(ch: *end--) >= 0) |
451 | return ERR_PTR(error: -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, num: &bitmap[chunk]); |
494 | #endif |
495 | if (IS_ERR(ptr: end)) |
496 | return PTR_ERR(ptr: end); |
497 | } |
498 | |
499 | unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32; |
500 | if (unset_bit < nmaskbits) { |
501 | bitmap_clear(map: maskp, start: unset_bit, nbits: nmaskbits - unset_bit); |
502 | return 0; |
503 | } |
504 | |
505 | if (find_next_bit(addr: maskp, size: unset_bit, offset: nmaskbits) != unset_bit) |
506 | return -EOVERFLOW; |
507 | |
508 | return 0; |
509 | } |
510 | EXPORT_SYMBOL(bitmap_parse); |
511 | |