projects/linux·blob v7.2-rc3 · refs

478 lines · 13.6 KiB

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