← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-ti-omap4/precise-security

« back to all changes in this revision

Viewing changes to tools/power/cpupower/utils/helpers/bitmask.c

  • Committer: Package Import Robot
  • Author(s): Paolo Pisati, Paolo Pisati
  • Date: 2011-12-06 15:56:07 UTC
  • Revision ID: package-import@ubuntu.com-20111206155607-pcf44kv5fmhk564f
Tags: 3.2.0-1401.1
[ Paolo Pisati ]

* Rebased on top of Ubuntu-3.2.0-3.8
* Tilt-tracking @ ef2487af4bb15bdd0689631774b5a5e3a59f74e2
* Delete debian.ti-omap4/control, it shoudln't be tracked
* Fix architecture spelling (s/armel/armhf/)
* [Config] Update configs following 3.2 import
* [Config] Fix compilation: disable CODA and ARCH_OMAP3
* [Config] Fix compilation: disable Ethernet Faraday
* Update series to precise

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/power/cpupower/utils/helpers/bitmask.c
 
1
#include <stdio.h>
 
2
#include <stdlib.h>
 
3
#include <string.h>
 
4
 
 
5
#include <helpers/bitmask.h>
 
6
 
 
7
/* How many bits in an unsigned long */
 
8
#define bitsperlong (8 * sizeof(unsigned long))
 
9
 
 
10
/* howmany(a,b) : how many elements of size b needed to hold all of a */
 
11
#define howmany(x, y) (((x)+((y)-1))/(y))
 
12
 
 
13
/* How many longs in mask of n bits */
 
14
#define longsperbits(n) howmany(n, bitsperlong)
 
15
 
 
16
#define max(a, b) ((a) > (b) ? (a) : (b))
 
17
 
 
18
/*
 
19
 * Allocate and free `struct bitmask *`
 
20
 */
 
21
 
 
22
/* Allocate a new `struct bitmask` with a size of n bits */
 
23
struct bitmask *bitmask_alloc(unsigned int n)
 
24
{
 
25
        struct bitmask *bmp;
 
26
 
 
27
        bmp = malloc(sizeof(*bmp));
 
28
        if (bmp == 0)
 
29
                return 0;
 
30
        bmp->size = n;
 
31
        bmp->maskp = calloc(longsperbits(n), sizeof(unsigned long));
 
32
        if (bmp->maskp == 0) {
 
33
                free(bmp);
 
34
                return 0;
 
35
        }
 
36
        return bmp;
 
37
}
 
38
 
 
39
/* Free `struct bitmask` */
 
40
void bitmask_free(struct bitmask *bmp)
 
41
{
 
42
        if (bmp == 0)
 
43
                return;
 
44
        free(bmp->maskp);
 
45
        bmp->maskp = (unsigned long *)0xdeadcdef;  /* double free tripwire */
 
46
        free(bmp);
 
47
}
 
48
 
 
49
/*
 
50
 * The routines _getbit() and _setbit() are the only
 
51
 * routines that actually understand the layout of bmp->maskp[].
 
52
 *
 
53
 * On little endian architectures, this could simply be an array of
 
54
 * bytes.  But the kernel layout of bitmasks _is_ visible to userspace
 
55
 * via the sched_(set/get)affinity calls in Linux 2.6, and on big
 
56
 * endian architectures, it is painfully obvious that this is an
 
57
 * array of unsigned longs.
 
58
 */
 
59
 
 
60
/* Return the value (0 or 1) of bit n in bitmask bmp */
 
61
static unsigned int _getbit(const struct bitmask *bmp, unsigned int n)
 
62
{
 
63
        if (n < bmp->size)
 
64
                return (bmp->maskp[n/bitsperlong] >> (n % bitsperlong)) & 1;
 
65
        else
 
66
                return 0;
 
67
}
 
68
 
 
69
/* Set bit n in bitmask bmp to value v (0 or 1) */
 
70
static void _setbit(struct bitmask *bmp, unsigned int n, unsigned int v)
 
71
{
 
72
        if (n < bmp->size) {
 
73
                if (v)
 
74
                        bmp->maskp[n/bitsperlong] |= 1UL << (n % bitsperlong);
 
75
                else
 
76
                        bmp->maskp[n/bitsperlong] &=
 
77
                                ~(1UL << (n % bitsperlong));
 
78
        }
 
79
}
 
80
 
 
81
/*
 
82
 * When parsing bitmask lists, only allow numbers, separated by one
 
83
 * of the allowed next characters.
 
84
 *
 
85
 * The parameter 'sret' is the return from a sscanf "%u%c".  It is
 
86
 * -1 if the sscanf input string was empty.  It is 0 if the first
 
87
 * character in the sscanf input string was not a decimal number.
 
88
 * It is 1 if the unsigned number matching the "%u" was the end of the
 
89
 * input string.  It is 2 if one or more additional characters followed
 
90
 * the matched unsigned number.  If it is 2, then 'nextc' is the first
 
91
 * character following the number.  The parameter 'ok_next_chars'
 
92
 * is the nul-terminated list of allowed next characters.
 
93
 *
 
94
 * The mask term just scanned was ok if and only if either the numbers
 
95
 * matching the %u were all of the input or if the next character in
 
96
 * the input past the numbers was one of the allowed next characters.
 
97
 */
 
98
static int scan_was_ok(int sret, char nextc, const char *ok_next_chars)
 
99
{
 
100
        return sret == 1 ||
 
101
                (sret == 2 && strchr(ok_next_chars, nextc) != NULL);
 
102
}
 
103
 
 
104
static const char *nexttoken(const char *q,  int sep)
 
105
{
 
106
        if (q)
 
107
                q = strchr(q, sep);
 
108
        if (q)
 
109
                q++;
 
110
        return q;
 
111
}
 
112
 
 
113
/* Set a single bit i in bitmask */
 
114
struct bitmask *bitmask_setbit(struct bitmask *bmp, unsigned int i)
 
115
{
 
116
        _setbit(bmp, i, 1);
 
117
        return bmp;
 
118
}
 
119
 
 
120
/* Set all bits in bitmask: bmp = ~0 */
 
121
struct bitmask *bitmask_setall(struct bitmask *bmp)
 
122
{
 
123
        unsigned int i;
 
124
        for (i = 0; i < bmp->size; i++)
 
125
                _setbit(bmp, i, 1);
 
126
        return bmp;
 
127
}
 
128
 
 
129
/* Clear all bits in bitmask: bmp = 0 */
 
130
struct bitmask *bitmask_clearall(struct bitmask *bmp)
 
131
{
 
132
        unsigned int i;
 
133
        for (i = 0; i < bmp->size; i++)
 
134
                _setbit(bmp, i, 0);
 
135
        return bmp;
 
136
}
 
137
 
 
138
/* True if all bits are clear */
 
139
int bitmask_isallclear(const struct bitmask *bmp)
 
140
{
 
141
        unsigned int i;
 
142
        for (i = 0; i < bmp->size; i++)
 
143
                if (_getbit(bmp, i))
 
144
                        return 0;
 
145
        return 1;
 
146
}
 
147
 
 
148
/* True if specified bit i is set */
 
149
int bitmask_isbitset(const struct bitmask *bmp, unsigned int i)
 
150
{
 
151
        return _getbit(bmp, i);
 
152
}
 
153
 
 
154
/* Number of lowest set bit (min) */
 
155
unsigned int bitmask_first(const struct bitmask *bmp)
 
156
{
 
157
        return bitmask_next(bmp, 0);
 
158
}
 
159
 
 
160
/* Number of highest set bit (max) */
 
161
unsigned int bitmask_last(const struct bitmask *bmp)
 
162
{
 
163
        unsigned int i;
 
164
        unsigned int m = bmp->size;
 
165
        for (i = 0; i < bmp->size; i++)
 
166
                if (_getbit(bmp, i))
 
167
                        m = i;
 
168
        return m;
 
169
}
 
170
 
 
171
/* Number of next set bit at or above given bit i */
 
172
unsigned int bitmask_next(const struct bitmask *bmp, unsigned int i)
 
173
{
 
174
        unsigned int n;
 
175
        for (n = i; n < bmp->size; n++)
 
176
                if (_getbit(bmp, n))
 
177
                        break;
 
178
        return n;
 
179
}
 
180
 
 
181
/*
 
182
 * Parses a comma-separated list of numbers and ranges of numbers,
 
183
 * with optional ':%u' strides modifying ranges, into provided bitmask.
 
184
 * Some examples of input lists and their equivalent simple list:
 
185
 *      Input           Equivalent to
 
186
 *      0-3             0,1,2,3
 
187
 *      0-7:2           0,2,4,6
 
188
 *      1,3,5-7         1,3,5,6,7
 
189
 *      0-3:2,8-15:4    0,2,8,12
 
190
 */
 
191
int bitmask_parselist(const char *buf, struct bitmask *bmp)
 
192
{
 
193
        const char *p, *q;
 
194
 
 
195
        bitmask_clearall(bmp);
 
196
 
 
197
        q = buf;
 
198
        while (p = q, q = nexttoken(q, ','), p) {
 
199
                unsigned int a;         /* begin of range */
 
200
                unsigned int b;         /* end of range */
 
201
                unsigned int s;         /* stride */
 
202
                const char *c1, *c2;    /* next tokens after '-' or ',' */
 
203
                char nextc;             /* char after sscanf %u match */
 
204
                int sret;               /* sscanf return (number of matches) */
 
205
 
 
206
                sret = sscanf(p, "%u%c", &a, &nextc);
 
207
                if (!scan_was_ok(sret, nextc, ",-"))
 
208
                        goto err;
 
209
                b = a;
 
210
                s = 1;
 
211
                c1 = nexttoken(p, '-');
 
212
                c2 = nexttoken(p, ',');
 
213
                if (c1 != NULL && (c2 == NULL || c1 < c2)) {
 
214
                        sret = sscanf(c1, "%u%c", &b, &nextc);
 
215
                        if (!scan_was_ok(sret, nextc, ",:"))
 
216
                                goto err;
 
217
                        c1 = nexttoken(c1, ':');
 
218
                        if (c1 != NULL && (c2 == NULL || c1 < c2)) {
 
219
                                sret = sscanf(c1, "%u%c", &s, &nextc);
 
220
                                if (!scan_was_ok(sret, nextc, ","))
 
221
                                        goto err;
 
222
                        }
 
223
                }
 
224
                if (!(a <= b))
 
225
                        goto err;
 
226
                if (b >= bmp->size)
 
227
                        goto err;
 
228
                while (a <= b) {
 
229
                        _setbit(bmp, a, 1);
 
230
                        a += s;
 
231
                }
 
232
        }
 
233
        return 0;
 
234
err:
 
235
        bitmask_clearall(bmp);
 
236
        return -1;
 
237
}
 
238
 
 
239
/*
 
240
 * emit(buf, buflen, rbot, rtop, len)
 
241
 *
 
242
 * Helper routine for bitmask_displaylist().  Write decimal number
 
243
 * or range to buf+len, suppressing output past buf+buflen, with optional
 
244
 * comma-prefix.  Return len of what would be written to buf, if it
 
245
 * all fit.
 
246
 */
 
247
 
 
248
static inline int emit(char *buf, int buflen, int rbot, int rtop, int len)
 
249
{
 
250
        if (len > 0)
 
251
                len += snprintf(buf + len, max(buflen - len, 0), ",");
 
252
        if (rbot == rtop)
 
253
                len += snprintf(buf + len, max(buflen - len, 0), "%d", rbot);
 
254
        else
 
255
                len += snprintf(buf + len, max(buflen - len, 0), "%d-%d",
 
256
                                rbot, rtop);
 
257
        return len;
 
258
}
 
259
 
 
260
/*
 
261
 * Write decimal list representation of bmp to buf.
 
262
 *
 
263
 * Output format is a comma-separated list of decimal numbers and
 
264
 * ranges.  Consecutively set bits are shown as two hyphen-separated
 
265
 * decimal numbers, the smallest and largest bit numbers set in
 
266
 * the range.  Output format is compatible with the format
 
267
 * accepted as input by bitmap_parselist().
 
268
 *
 
269
 * The return value is the number of characters which would be
 
270
 * generated for the given input, excluding the trailing '\0', as
 
271
 * per ISO C99.
 
272
 */
 
273
 
 
274
int bitmask_displaylist(char *buf, int buflen, const struct bitmask *bmp)
 
275
{
 
276
        int len = 0;
 
277
        /* current bit is 'cur', most recently seen range is [rbot, rtop] */
 
278
        unsigned int cur, rbot, rtop;
 
279
 
 
280
        if (buflen > 0)
 
281
                *buf = 0;
 
282
        rbot = cur = bitmask_first(bmp);
 
283
        while (cur < bmp->size) {
 
284
                rtop = cur;
 
285
                cur = bitmask_next(bmp, cur+1);
 
286
                if (cur >= bmp->size || cur > rtop + 1) {
 
287
                        len = emit(buf, buflen, rbot, rtop, len);
 
288
                        rbot = cur;
 
289
                }
 
290
        }
 
291
        return len;
 
292
}