Commit | Line | Data |
---|---|---|
aae06fc1 YN |
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); |