1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
27fe2f639SDominik Brodowski #include <stdio.h>
37fe2f639SDominik Brodowski #include <stdlib.h>
47fe2f639SDominik Brodowski #include <string.h>
57fe2f639SDominik Brodowski
67fe2f639SDominik Brodowski #include <helpers/bitmask.h>
77fe2f639SDominik Brodowski
87fe2f639SDominik Brodowski /* How many bits in an unsigned long */
97fe2f639SDominik Brodowski #define bitsperlong (8 * sizeof(unsigned long))
107fe2f639SDominik Brodowski
117fe2f639SDominik Brodowski /* howmany(a,b) : how many elements of size b needed to hold all of a */
127fe2f639SDominik Brodowski #define howmany(x, y) (((x)+((y)-1))/(y))
137fe2f639SDominik Brodowski
147fe2f639SDominik Brodowski /* How many longs in mask of n bits */
157fe2f639SDominik Brodowski #define longsperbits(n) howmany(n, bitsperlong)
167fe2f639SDominik Brodowski
177fe2f639SDominik Brodowski #define max(a, b) ((a) > (b) ? (a) : (b))
187fe2f639SDominik Brodowski
197fe2f639SDominik Brodowski /*
207fe2f639SDominik Brodowski * Allocate and free `struct bitmask *`
217fe2f639SDominik Brodowski */
227fe2f639SDominik Brodowski
237fe2f639SDominik Brodowski /* Allocate a new `struct bitmask` with a size of n bits */
bitmask_alloc(unsigned int n)247fe2f639SDominik Brodowski struct bitmask *bitmask_alloc(unsigned int n)
257fe2f639SDominik Brodowski {
267fe2f639SDominik Brodowski struct bitmask *bmp;
277fe2f639SDominik Brodowski
287fe2f639SDominik Brodowski bmp = malloc(sizeof(*bmp));
29*8e022709SShuah Khan if (!bmp)
307fe2f639SDominik Brodowski return 0;
317fe2f639SDominik Brodowski bmp->size = n;
327fe2f639SDominik Brodowski bmp->maskp = calloc(longsperbits(n), sizeof(unsigned long));
33*8e022709SShuah Khan if (!bmp->maskp) {
347fe2f639SDominik Brodowski free(bmp);
357fe2f639SDominik Brodowski return 0;
367fe2f639SDominik Brodowski }
377fe2f639SDominik Brodowski return bmp;
387fe2f639SDominik Brodowski }
397fe2f639SDominik Brodowski
407fe2f639SDominik Brodowski /* Free `struct bitmask` */
bitmask_free(struct bitmask * bmp)417fe2f639SDominik Brodowski void bitmask_free(struct bitmask *bmp)
427fe2f639SDominik Brodowski {
43*8e022709SShuah Khan if (!bmp)
447fe2f639SDominik Brodowski return;
457fe2f639SDominik Brodowski free(bmp->maskp);
467fe2f639SDominik Brodowski bmp->maskp = (unsigned long *)0xdeadcdef; /* double free tripwire */
477fe2f639SDominik Brodowski free(bmp);
487fe2f639SDominik Brodowski }
497fe2f639SDominik Brodowski
507fe2f639SDominik Brodowski /*
517fe2f639SDominik Brodowski * The routines _getbit() and _setbit() are the only
527fe2f639SDominik Brodowski * routines that actually understand the layout of bmp->maskp[].
537fe2f639SDominik Brodowski *
547fe2f639SDominik Brodowski * On little endian architectures, this could simply be an array of
557fe2f639SDominik Brodowski * bytes. But the kernel layout of bitmasks _is_ visible to userspace
567fe2f639SDominik Brodowski * via the sched_(set/get)affinity calls in Linux 2.6, and on big
577fe2f639SDominik Brodowski * endian architectures, it is painfully obvious that this is an
587fe2f639SDominik Brodowski * array of unsigned longs.
597fe2f639SDominik Brodowski */
607fe2f639SDominik Brodowski
617fe2f639SDominik Brodowski /* Return the value (0 or 1) of bit n in bitmask bmp */
_getbit(const struct bitmask * bmp,unsigned int n)627fe2f639SDominik Brodowski static unsigned int _getbit(const struct bitmask *bmp, unsigned int n)
637fe2f639SDominik Brodowski {
647fe2f639SDominik Brodowski if (n < bmp->size)
657fe2f639SDominik Brodowski return (bmp->maskp[n/bitsperlong] >> (n % bitsperlong)) & 1;
667fe2f639SDominik Brodowski else
677fe2f639SDominik Brodowski return 0;
687fe2f639SDominik Brodowski }
697fe2f639SDominik Brodowski
707fe2f639SDominik Brodowski /* Set bit n in bitmask bmp to value v (0 or 1) */
_setbit(struct bitmask * bmp,unsigned int n,unsigned int v)717fe2f639SDominik Brodowski static void _setbit(struct bitmask *bmp, unsigned int n, unsigned int v)
727fe2f639SDominik Brodowski {
737fe2f639SDominik Brodowski if (n < bmp->size) {
747fe2f639SDominik Brodowski if (v)
757fe2f639SDominik Brodowski bmp->maskp[n/bitsperlong] |= 1UL << (n % bitsperlong);
767fe2f639SDominik Brodowski else
772cd005caSDominik Brodowski bmp->maskp[n/bitsperlong] &=
782cd005caSDominik Brodowski ~(1UL << (n % bitsperlong));
797fe2f639SDominik Brodowski }
807fe2f639SDominik Brodowski }
817fe2f639SDominik Brodowski
827fe2f639SDominik Brodowski /*
837fe2f639SDominik Brodowski * When parsing bitmask lists, only allow numbers, separated by one
847fe2f639SDominik Brodowski * of the allowed next characters.
857fe2f639SDominik Brodowski *
867fe2f639SDominik Brodowski * The parameter 'sret' is the return from a sscanf "%u%c". It is
877fe2f639SDominik Brodowski * -1 if the sscanf input string was empty. It is 0 if the first
887fe2f639SDominik Brodowski * character in the sscanf input string was not a decimal number.
897fe2f639SDominik Brodowski * It is 1 if the unsigned number matching the "%u" was the end of the
907fe2f639SDominik Brodowski * input string. It is 2 if one or more additional characters followed
917fe2f639SDominik Brodowski * the matched unsigned number. If it is 2, then 'nextc' is the first
927fe2f639SDominik Brodowski * character following the number. The parameter 'ok_next_chars'
937fe2f639SDominik Brodowski * is the nul-terminated list of allowed next characters.
947fe2f639SDominik Brodowski *
957fe2f639SDominik Brodowski * The mask term just scanned was ok if and only if either the numbers
967fe2f639SDominik Brodowski * matching the %u were all of the input or if the next character in
977fe2f639SDominik Brodowski * the input past the numbers was one of the allowed next characters.
987fe2f639SDominik Brodowski */
scan_was_ok(int sret,char nextc,const char * ok_next_chars)997fe2f639SDominik Brodowski static int scan_was_ok(int sret, char nextc, const char *ok_next_chars)
1007fe2f639SDominik Brodowski {
1017fe2f639SDominik Brodowski return sret == 1 ||
1027fe2f639SDominik Brodowski (sret == 2 && strchr(ok_next_chars, nextc) != NULL);
1037fe2f639SDominik Brodowski }
1047fe2f639SDominik Brodowski
nexttoken(const char * q,int sep)1057fe2f639SDominik Brodowski static const char *nexttoken(const char *q, int sep)
1067fe2f639SDominik Brodowski {
1077fe2f639SDominik Brodowski if (q)
1087fe2f639SDominik Brodowski q = strchr(q, sep);
1097fe2f639SDominik Brodowski if (q)
1107fe2f639SDominik Brodowski q++;
1117fe2f639SDominik Brodowski return q;
1127fe2f639SDominik Brodowski }
1137fe2f639SDominik Brodowski
1147fe2f639SDominik Brodowski /* Set a single bit i in bitmask */
bitmask_setbit(struct bitmask * bmp,unsigned int i)1157fe2f639SDominik Brodowski struct bitmask *bitmask_setbit(struct bitmask *bmp, unsigned int i)
1167fe2f639SDominik Brodowski {
1177fe2f639SDominik Brodowski _setbit(bmp, i, 1);
1187fe2f639SDominik Brodowski return bmp;
1197fe2f639SDominik Brodowski }
1207fe2f639SDominik Brodowski
1217fe2f639SDominik Brodowski /* Set all bits in bitmask: bmp = ~0 */
bitmask_setall(struct bitmask * bmp)1227fe2f639SDominik Brodowski struct bitmask *bitmask_setall(struct bitmask *bmp)
1237fe2f639SDominik Brodowski {
1247fe2f639SDominik Brodowski unsigned int i;
1257fe2f639SDominik Brodowski for (i = 0; i < bmp->size; i++)
1267fe2f639SDominik Brodowski _setbit(bmp, i, 1);
1277fe2f639SDominik Brodowski return bmp;
1287fe2f639SDominik Brodowski }
1297fe2f639SDominik Brodowski
1307fe2f639SDominik Brodowski /* Clear all bits in bitmask: bmp = 0 */
bitmask_clearall(struct bitmask * bmp)1317fe2f639SDominik Brodowski struct bitmask *bitmask_clearall(struct bitmask *bmp)
1327fe2f639SDominik Brodowski {
1337fe2f639SDominik Brodowski unsigned int i;
1347fe2f639SDominik Brodowski for (i = 0; i < bmp->size; i++)
1357fe2f639SDominik Brodowski _setbit(bmp, i, 0);
1367fe2f639SDominik Brodowski return bmp;
1377fe2f639SDominik Brodowski }
1387fe2f639SDominik Brodowski
1397fe2f639SDominik Brodowski /* True if all bits are clear */
bitmask_isallclear(const struct bitmask * bmp)1407fe2f639SDominik Brodowski int bitmask_isallclear(const struct bitmask *bmp)
1417fe2f639SDominik Brodowski {
1427fe2f639SDominik Brodowski unsigned int i;
1437fe2f639SDominik Brodowski for (i = 0; i < bmp->size; i++)
1447fe2f639SDominik Brodowski if (_getbit(bmp, i))
1457fe2f639SDominik Brodowski return 0;
1467fe2f639SDominik Brodowski return 1;
1477fe2f639SDominik Brodowski }
1487fe2f639SDominik Brodowski
1497fe2f639SDominik Brodowski /* True if specified bit i is set */
bitmask_isbitset(const struct bitmask * bmp,unsigned int i)1507fe2f639SDominik Brodowski int bitmask_isbitset(const struct bitmask *bmp, unsigned int i)
1517fe2f639SDominik Brodowski {
1527fe2f639SDominik Brodowski return _getbit(bmp, i);
1537fe2f639SDominik Brodowski }
1547fe2f639SDominik Brodowski
1557fe2f639SDominik Brodowski /* Number of lowest set bit (min) */
bitmask_first(const struct bitmask * bmp)1567fe2f639SDominik Brodowski unsigned int bitmask_first(const struct bitmask *bmp)
1577fe2f639SDominik Brodowski {
1587fe2f639SDominik Brodowski return bitmask_next(bmp, 0);
1597fe2f639SDominik Brodowski }
1607fe2f639SDominik Brodowski
1617fe2f639SDominik Brodowski /* Number of highest set bit (max) */
bitmask_last(const struct bitmask * bmp)1627fe2f639SDominik Brodowski unsigned int bitmask_last(const struct bitmask *bmp)
1637fe2f639SDominik Brodowski {
1647fe2f639SDominik Brodowski unsigned int i;
1657fe2f639SDominik Brodowski unsigned int m = bmp->size;
1667fe2f639SDominik Brodowski for (i = 0; i < bmp->size; i++)
1677fe2f639SDominik Brodowski if (_getbit(bmp, i))
1687fe2f639SDominik Brodowski m = i;
1697fe2f639SDominik Brodowski return m;
1707fe2f639SDominik Brodowski }
1717fe2f639SDominik Brodowski
1727fe2f639SDominik Brodowski /* Number of next set bit at or above given bit i */
bitmask_next(const struct bitmask * bmp,unsigned int i)1737fe2f639SDominik Brodowski unsigned int bitmask_next(const struct bitmask *bmp, unsigned int i)
1747fe2f639SDominik Brodowski {
1757fe2f639SDominik Brodowski unsigned int n;
1767fe2f639SDominik Brodowski for (n = i; n < bmp->size; n++)
1777fe2f639SDominik Brodowski if (_getbit(bmp, n))
1787fe2f639SDominik Brodowski break;
1797fe2f639SDominik Brodowski return n;
1807fe2f639SDominik Brodowski }
1817fe2f639SDominik Brodowski
1827fe2f639SDominik Brodowski /*
1837fe2f639SDominik Brodowski * Parses a comma-separated list of numbers and ranges of numbers,
1847fe2f639SDominik Brodowski * with optional ':%u' strides modifying ranges, into provided bitmask.
1857fe2f639SDominik Brodowski * Some examples of input lists and their equivalent simple list:
1867fe2f639SDominik Brodowski * Input Equivalent to
1877fe2f639SDominik Brodowski * 0-3 0,1,2,3
1887fe2f639SDominik Brodowski * 0-7:2 0,2,4,6
1897fe2f639SDominik Brodowski * 1,3,5-7 1,3,5,6,7
1907fe2f639SDominik Brodowski * 0-3:2,8-15:4 0,2,8,12
1917fe2f639SDominik Brodowski */
bitmask_parselist(const char * buf,struct bitmask * bmp)1927fe2f639SDominik Brodowski int bitmask_parselist(const char *buf, struct bitmask *bmp)
1937fe2f639SDominik Brodowski {
1947fe2f639SDominik Brodowski const char *p, *q;
1957fe2f639SDominik Brodowski
1967fe2f639SDominik Brodowski bitmask_clearall(bmp);
1977fe2f639SDominik Brodowski
1987fe2f639SDominik Brodowski q = buf;
1997fe2f639SDominik Brodowski while (p = q, q = nexttoken(q, ','), p) {
2007fe2f639SDominik Brodowski unsigned int a; /* begin of range */
2017fe2f639SDominik Brodowski unsigned int b; /* end of range */
2027fe2f639SDominik Brodowski unsigned int s; /* stride */
2037fe2f639SDominik Brodowski const char *c1, *c2; /* next tokens after '-' or ',' */
2047fe2f639SDominik Brodowski char nextc; /* char after sscanf %u match */
2057fe2f639SDominik Brodowski int sret; /* sscanf return (number of matches) */
2067fe2f639SDominik Brodowski
2077fe2f639SDominik Brodowski sret = sscanf(p, "%u%c", &a, &nextc);
2087fe2f639SDominik Brodowski if (!scan_was_ok(sret, nextc, ",-"))
2097fe2f639SDominik Brodowski goto err;
2107fe2f639SDominik Brodowski b = a;
2117fe2f639SDominik Brodowski s = 1;
2127fe2f639SDominik Brodowski c1 = nexttoken(p, '-');
2137fe2f639SDominik Brodowski c2 = nexttoken(p, ',');
2147fe2f639SDominik Brodowski if (c1 != NULL && (c2 == NULL || c1 < c2)) {
2157fe2f639SDominik Brodowski sret = sscanf(c1, "%u%c", &b, &nextc);
2167fe2f639SDominik Brodowski if (!scan_was_ok(sret, nextc, ",:"))
2177fe2f639SDominik Brodowski goto err;
2187fe2f639SDominik Brodowski c1 = nexttoken(c1, ':');
2197fe2f639SDominik Brodowski if (c1 != NULL && (c2 == NULL || c1 < c2)) {
2207fe2f639SDominik Brodowski sret = sscanf(c1, "%u%c", &s, &nextc);
2217fe2f639SDominik Brodowski if (!scan_was_ok(sret, nextc, ","))
2227fe2f639SDominik Brodowski goto err;
2237fe2f639SDominik Brodowski }
2247fe2f639SDominik Brodowski }
2257fe2f639SDominik Brodowski if (!(a <= b))
2267fe2f639SDominik Brodowski goto err;
2277fe2f639SDominik Brodowski if (b >= bmp->size)
2287fe2f639SDominik Brodowski goto err;
2297fe2f639SDominik Brodowski while (a <= b) {
2307fe2f639SDominik Brodowski _setbit(bmp, a, 1);
2317fe2f639SDominik Brodowski a += s;
2327fe2f639SDominik Brodowski }
2337fe2f639SDominik Brodowski }
2347fe2f639SDominik Brodowski return 0;
2357fe2f639SDominik Brodowski err:
2367fe2f639SDominik Brodowski bitmask_clearall(bmp);
2377fe2f639SDominik Brodowski return -1;
2387fe2f639SDominik Brodowski }
2397fe2f639SDominik Brodowski
2407fe2f639SDominik Brodowski /*
2417fe2f639SDominik Brodowski * emit(buf, buflen, rbot, rtop, len)
2427fe2f639SDominik Brodowski *
2437fe2f639SDominik Brodowski * Helper routine for bitmask_displaylist(). Write decimal number
2447fe2f639SDominik Brodowski * or range to buf+len, suppressing output past buf+buflen, with optional
2457fe2f639SDominik Brodowski * comma-prefix. Return len of what would be written to buf, if it
2467fe2f639SDominik Brodowski * all fit.
2477fe2f639SDominik Brodowski */
2487fe2f639SDominik Brodowski
emit(char * buf,int buflen,int rbot,int rtop,int len)2497fe2f639SDominik Brodowski static inline int emit(char *buf, int buflen, int rbot, int rtop, int len)
2507fe2f639SDominik Brodowski {
2517fe2f639SDominik Brodowski if (len > 0)
2527fe2f639SDominik Brodowski len += snprintf(buf + len, max(buflen - len, 0), ",");
2537fe2f639SDominik Brodowski if (rbot == rtop)
2547fe2f639SDominik Brodowski len += snprintf(buf + len, max(buflen - len, 0), "%d", rbot);
2557fe2f639SDominik Brodowski else
2562cd005caSDominik Brodowski len += snprintf(buf + len, max(buflen - len, 0), "%d-%d",
2572cd005caSDominik Brodowski rbot, rtop);
2587fe2f639SDominik Brodowski return len;
2597fe2f639SDominik Brodowski }
2607fe2f639SDominik Brodowski
2617fe2f639SDominik Brodowski /*
2627fe2f639SDominik Brodowski * Write decimal list representation of bmp to buf.
2637fe2f639SDominik Brodowski *
2647fe2f639SDominik Brodowski * Output format is a comma-separated list of decimal numbers and
2657fe2f639SDominik Brodowski * ranges. Consecutively set bits are shown as two hyphen-separated
2667fe2f639SDominik Brodowski * decimal numbers, the smallest and largest bit numbers set in
2677fe2f639SDominik Brodowski * the range. Output format is compatible with the format
2687fe2f639SDominik Brodowski * accepted as input by bitmap_parselist().
2697fe2f639SDominik Brodowski *
2707fe2f639SDominik Brodowski * The return value is the number of characters which would be
2717fe2f639SDominik Brodowski * generated for the given input, excluding the trailing '\0', as
2727fe2f639SDominik Brodowski * per ISO C99.
2737fe2f639SDominik Brodowski */
2747fe2f639SDominik Brodowski
bitmask_displaylist(char * buf,int buflen,const struct bitmask * bmp)2757fe2f639SDominik Brodowski int bitmask_displaylist(char *buf, int buflen, const struct bitmask *bmp)
2767fe2f639SDominik Brodowski {
2777fe2f639SDominik Brodowski int len = 0;
2787fe2f639SDominik Brodowski /* current bit is 'cur', most recently seen range is [rbot, rtop] */
2797fe2f639SDominik Brodowski unsigned int cur, rbot, rtop;
2807fe2f639SDominik Brodowski
2817fe2f639SDominik Brodowski if (buflen > 0)
2827fe2f639SDominik Brodowski *buf = 0;
2837fe2f639SDominik Brodowski rbot = cur = bitmask_first(bmp);
2847fe2f639SDominik Brodowski while (cur < bmp->size) {
2857fe2f639SDominik Brodowski rtop = cur;
2867fe2f639SDominik Brodowski cur = bitmask_next(bmp, cur+1);
2877fe2f639SDominik Brodowski if (cur >= bmp->size || cur > rtop + 1) {
2887fe2f639SDominik Brodowski len = emit(buf, buflen, rbot, rtop, len);
2897fe2f639SDominik Brodowski rbot = cur;
2907fe2f639SDominik Brodowski }
2917fe2f639SDominik Brodowski }
2927fe2f639SDominik Brodowski return len;
2937fe2f639SDominik Brodowski }
294