1 // SPDX-License-Identifier: GPL-2.0-only 1
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 st
17 *
18 * @ubuf: pointer to user buffer containing st
19 * @ulen: buffer size in bytes. If string is
20 * then it must be terminated with a \0.
21 * @maskp: pointer to bitmap array that will c
22 * @nmaskbits: size of bitmap, in bits.
23 */
24 int bitmap_parse_user(const char __user *ubuf,
25 unsigned int ulen, uns
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, mask
36
37 kfree(buf);
38 return ret;
39 }
40 EXPORT_SYMBOL(bitmap_parse_user);
41
42 /**
43 * bitmap_print_to_pagebuf - convert bitmap to
44 * @list: indicates whether the bitmap must be
45 * @buf: page aligned buffer into which string
46 * @maskp: pointer to bitmap to convert
47 * @nmaskbits: size of bitmap, in bits
48 *
49 * Output format is a comma-separated list of
50 * ranges if list is specified or hex digits g
51 * sets of 8 digits/set. Returns the number of
52 *
53 * It is assumed that @buf is a pointer into a
54 * area and that sufficient storage remains at
55 * bitmap_print_to_pagebuf() output. Returns t
56 * actually printed to @buf, excluding termina
57 */
58 int bitmap_print_to_pagebuf(bool list, char *b
59 int nmaskbits)
60 {
61 ptrdiff_t len = PAGE_SIZE - offset_in_
62
63 return list ? scnprintf(buf, len, "%*p
64 scnprintf(buf, len, "%*p
65 }
66 EXPORT_SYMBOL(bitmap_print_to_pagebuf);
67
68 /**
69 * bitmap_print_to_buf - convert bitmap to li
70 * @list: indicates whether the bitmap must be
71 * true: print in decimal list format
72 * false: print in hexadecimal bitmask fo
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 copyi
77 * @count: the maximum number of bytes to prin
78 */
79 static int bitmap_print_to_buf(bool list, char
80 int nmaskbits, loff_t off, siz
81 {
82 const char *fmt = list ? "%*pbl\n" : "
83 ssize_t size;
84 void *data;
85
86 data = kasprintf(GFP_KERNEL, fmt, nmas
87 if (!data)
88 return -ENOMEM;
89
90 size = memory_read_from_buffer(buf, co
91 kfree(data);
92
93 return size;
94 }
95
96 /**
97 * bitmap_print_bitmask_to_buf - convert bitm
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 copyi
102 * @count: the maximum number of bytes to prin
103 *
104 * The bitmap_print_to_pagebuf() is used indir
105 * cpumap_print_to_pagebuf() or directly by dr
106 * bitmask and decimal list to userspace by sy
107 * Drivers might be using a normal attribute f
108 * normal attribute typically has show entry a
109 *
110 * static ssize_t example_attribute_show(str
111 * struct device_attribute *attr,
112 * {
113 * ...
114 * return bitmap_print_to_pagebuf(true, b
115 * }
116 *
117 * show entry of attribute has no offset and c
118 * means the file is limited to one page only.
119 * bitmap_print_to_pagebuf() API works terribl
120 * normal attribute with buf parameter and wit
121 *
122 * bitmap_print_to_pagebuf(bool list, char *
123 * int nmaskbits)
124 * {
125 * }
126 *
127 * The problem is once we have a large bitmap,
128 * bitmask or list more than one page. Especia
129 * as complex as 0,3,5,7,9,... We have no simp
130 * It turns out bin_attribute is a way to brea
131 * has show entry as below::
132 *
133 * static ssize_t
134 * example_bin_attribute_show(struct file *f
135 * struct bin_attribute *attr, ch
136 * loff_t offset, size_t count)
137 * {
138 * ...
139 * }
140 *
141 * With the new offset and count parameters, t
142 * to support file size more than one page. Fo
143 * >= 4096.
144 * bitmap_print_bitmask_to_buf(), bitmap_print
145 * cpumap wrapper cpumap_print_bitmask_to_buf(
146 * make those drivers be able to support large
147 * move to use bin_attribute. In result, we ha
148 * parameters such as off, count from bin_attr
149 *
150 * The role of cpumap_print_bitmask_to_buf() a
151 * is similar with cpumap_print_to_pagebuf(),
152 * bitmap_print_to_pagebuf() mainly serves sys
153 * the destination buffer is exactly one page
154 * cpumap_print_bitmask_to_buf() and cpumap_pr
155 * hand, mainly serves bin_attribute which doe
156 * and it can break the size limit of converte
157 * bitmask.
158 *
159 * WARNING!
160 *
161 * This function is not a replacement for spri
162 * It is intended to workaround sysfs limitati
163 * used carefully in general case for the foll
164 *
165 * - Time complexity is O(nbits^2/count), com
166 * - Memory complexity is O(nbits), comparing
167 * - @off and @count are NOT offset and numbe
168 * - If printing part of bitmap as list, the
169 * list representation of bitmap. Particula
170 * related interval may be erroneously set
171 * may be broken, so bitmap_parselist-like
172 * - If printing the whole bitmap as list by
173 * of calls of the function such that the o
174 * - If printing the whole bitmap as list by
175 * unchanged between the very first and ver
176 * result may be incorrect, and format may
177 *
178 * Returns the number of characters actually p
179 */
180 int bitmap_print_bitmask_to_buf(char *buf, con
181 int nmaskbits,
182 {
183 return bitmap_print_to_buf(false, buf,
184 }
185 EXPORT_SYMBOL(bitmap_print_bitmask_to_buf);
186
187 /**
188 * bitmap_print_list_to_buf - convert bitmap
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 copyi
193 * @count: the maximum number of bytes to prin
194 *
195 * Everything is same with the above bitmap_pr
196 * the print format.
197 */
198 int bitmap_print_list_to_buf(char *buf, const
199 int nmaskbits, lo
200 {
201 return bitmap_print_to_buf(true, buf,
202 }
203 EXPORT_SYMBOL(bitmap_print_list_to_buf);
204
205 /*
206 * Region 9-38:4/10 describes the following bi
207 * 0 9 12 18 38
208 * .........****......****......****..........
209 * ^ ^ ^ ^
210 * start off group_len end
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 reg
221 {
222 unsigned int start;
223
224 for (start = r->start; start <= r->end
225 bitmap_set(bitmap, start, min(
226 }
227
228 static int bitmap_check_region(const struct re
229 {
230 if (r->start > r->end || 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 *s
240 unsigned int
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 != (un
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_st
273 }
274
275 /*
276 * The format allows commas and whitespaces at
277 * of the region.
278 */
279 static const char *bitmap_find_region(const ch
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(
288 {
289 while (start <= end && __end_of_region
290 end--;
291
292 return end;
293 }
294
295 static const char *bitmap_parse_region(const c
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, la
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,
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,
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->grou
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 ASCI
348 * @buf: read user string from this buffer; mu
349 * with a \0 or \n.
350 * @maskp: write resulting mask here
351 * @nmaskbits: number of bits in mask to be wr
352 *
353 * Input format is a comma-separated list of d
354 * ranges. Consecutively set bits are shown a
355 * decimal numbers, the smallest and largest b
356 * the range.
357 * Optionally each range can be postfixed to d
358 * should be set. The range will divided to gr
359 * From each group will be used only defined a
360 * Syntax: range:used_size/group_size
361 * Example: 0-1023:2/256 ==> 0,1,256,257,512,5
362 * The value 'N' can be used as a dynamically
363 * maximum allowed value; i.e (nmaskbits - 1).
364 * dynamic, so if system changes cause the bit
365 * as more cores in a CPU list, then any range
366 *
367 * Returns: 0 on success, -errno on invalid in
368 *
369 * - ``-EINVAL``: wrong region format
370 * - ``-EINVAL``: invalid character in strin
371 * - ``-ERANGE``: bit number specified too l
372 * - ``-EOVERFLOW``: integer overflow in the
373 */
374 int bitmap_parselist(const char *buf, unsigned
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,
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 buff
405 * string to bitmap
406 *
407 * @ubuf: pointer to user buffer containing st
408 * @ulen: buffer size in bytes. If string is
409 * then it must be terminated with a \0.
410 * @maskp: pointer to bitmap array that will c
411 * @nmaskbits: size of bitmap, in bits.
412 *
413 * Wrapper for bitmap_parselist(), providing i
414 */
415 int bitmap_parselist_user(const char __user *u
416 unsigned int ulen, uns
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, nma
427
428 kfree(buf);
429 return ret;
430 }
431 EXPORT_SYMBOL(bitmap_parselist_user);
432
433 static const char *bitmap_get_x32_reverse(cons
434 const
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_re
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
459 * @start: pointer to buffer containing string
460 * @buflen: buffer size in bytes. If string i
461 * then it must be terminated with a \0 or
462 * UINT_MAX may be provided instead of stri
463 * @maskp: pointer to bitmap array that will c
464 * @nmaskbits: size of bitmap, in bits.
465 *
466 * Commas group hex digits into chunks. Each
467 * bits of the resultant bitmask. No chunk ma
468 * than 32 bits (%-EOVERFLOW), and if a chunk
469 * then leading 0-bits are prepended. %-EINVA
470 * characters. Grouping such as "1,,5", ",44",
471 * Leading, embedded and trailing whitespace a
472 */
473 int bitmap_parse(const char *start, unsigned i
474 unsigned long *maskp, int nmas
475 {
476 const char *end = strnchrnul(start, bu
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_rever
484 if (start > end)
485 break;
486
487 if (!chunks--)
488 return -EOVERFLOW;
489
490 #if defined(CONFIG_64BIT) && defined(__BIG_END
491 end = bitmap_get_x32_reverse(s
492 #else
493 end = bitmap_get_x32_reverse(s
494 #endif
495 if (IS_ERR(end))
496 return PTR_ERR(end);
497 }
498
499 unset_bit = (BITS_TO_U32(nmaskbits) -
500 if (unset_bit < nmaskbits) {
501 bitmap_clear(maskp, unset_bit,
502 return 0;
503 }
504
505 if (find_next_bit(maskp, unset_bit, nm
506 return -EOVERFLOW;
507
508 return 0;
509 }
510 EXPORT_SYMBOL(bitmap_parse);
511
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.