Branch data Line data Source code
1 : : /*
2 : : * Implementation of the extensible bitmap type.
3 : : *
4 : : * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5 : : */
6 : : /*
7 : : * Updated: Hewlett-Packard <paul@paul-moore.com>
8 : : *
9 : : * Added support to import/export the NetLabel category bitmap
10 : : *
11 : : * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
12 : : */
13 : : /*
14 : : * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
15 : : * Applied standard bit operations to improve bitmap scanning.
16 : : */
17 : :
18 : : #include <linux/kernel.h>
19 : : #include <linux/slab.h>
20 : : #include <linux/errno.h>
21 : : #include <net/netlabel.h>
22 : : #include "ebitmap.h"
23 : : #include "policydb.h"
24 : :
25 : : #define BITS_PER_U64 (sizeof(u64) * 8)
26 : :
27 : 0 : int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
28 : : {
29 : : struct ebitmap_node *n1, *n2;
30 : :
31 [ # # ]: 0 : if (e1->highbit != e2->highbit)
32 : : return 0;
33 : :
34 : 0 : n1 = e1->node;
35 : 0 : n2 = e2->node;
36 [ # # ][ # # ]: 0 : while (n1 && n2 &&
37 [ # # ]: 0 : (n1->startbit == n2->startbit) &&
38 : 0 : !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
39 : 0 : n1 = n1->next;
40 : 0 : n2 = n2->next;
41 : : }
42 : :
43 [ # # ]: 0 : if (n1 || n2)
44 : : return 0;
45 : :
46 : 0 : return 1;
47 : : }
48 : :
49 : 0 : int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
50 : : {
51 : : struct ebitmap_node *n, *new, *prev;
52 : :
53 : : ebitmap_init(dst);
54 : 0 : n = src->node;
55 : : prev = NULL;
56 [ # # ]: 0 : while (n) {
57 : : new = kzalloc(sizeof(*new), GFP_ATOMIC);
58 [ # # ]: 0 : if (!new) {
59 : 0 : ebitmap_destroy(dst);
60 : 0 : return -ENOMEM;
61 : : }
62 : 0 : new->startbit = n->startbit;
63 : 0 : memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
64 : 0 : new->next = NULL;
65 [ # # ]: 0 : if (prev)
66 : 0 : prev->next = new;
67 : : else
68 : 0 : dst->node = new;
69 : : prev = new;
70 : 0 : n = n->next;
71 : : }
72 : :
73 : 0 : dst->highbit = src->highbit;
74 : 0 : return 0;
75 : : }
76 : :
77 : : #ifdef CONFIG_NETLABEL
78 : : /**
79 : : * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
80 : : * @ebmap: the ebitmap to export
81 : : * @catmap: the NetLabel category bitmap
82 : : *
83 : : * Description:
84 : : * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
85 : : * Returns zero on success, negative values on error.
86 : : *
87 : : */
88 : 0 : int ebitmap_netlbl_export(struct ebitmap *ebmap,
89 : : struct netlbl_lsm_secattr_catmap **catmap)
90 : : {
91 : 0 : struct ebitmap_node *e_iter = ebmap->node;
92 : : struct netlbl_lsm_secattr_catmap *c_iter;
93 : : u32 cmap_idx, cmap_sft;
94 : : int i;
95 : :
96 : : /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
97 : : * however, it is not always compatible with an array of unsigned long
98 : : * in ebitmap_node.
99 : : * In addition, you should pay attention the following implementation
100 : : * assumes unsigned long has a width equal with or less than 64-bit.
101 : : */
102 : :
103 [ # # ]: 0 : if (e_iter == NULL) {
104 : 0 : *catmap = NULL;
105 : 0 : return 0;
106 : : }
107 : :
108 : : c_iter = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
109 [ # # ]: 0 : if (c_iter == NULL)
110 : : return -ENOMEM;
111 : 0 : *catmap = c_iter;
112 : 0 : c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1);
113 : :
114 [ # # ]: 0 : while (e_iter) {
115 [ # # ]: 0 : for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
116 : : unsigned int delta, e_startbit, c_endbit;
117 : :
118 : 0 : e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE;
119 : 0 : c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE;
120 [ # # ]: 0 : if (e_startbit >= c_endbit) {
121 : : c_iter->next
122 : 0 : = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
123 [ # # ]: 0 : if (c_iter->next == NULL)
124 : : goto netlbl_export_failure;
125 : : c_iter = c_iter->next;
126 : : c_iter->startbit
127 : 0 : = e_startbit & ~(NETLBL_CATMAP_SIZE - 1);
128 : : }
129 : 0 : delta = e_startbit - c_iter->startbit;
130 : 0 : cmap_idx = delta / NETLBL_CATMAP_MAPSIZE;
131 : 0 : cmap_sft = delta % NETLBL_CATMAP_MAPSIZE;
132 : : c_iter->bitmap[cmap_idx]
133 : 0 : |= e_iter->maps[i] << cmap_sft;
134 : : }
135 : 0 : e_iter = e_iter->next;
136 : : }
137 : :
138 : : return 0;
139 : :
140 : : netlbl_export_failure:
141 : 0 : netlbl_secattr_catmap_free(*catmap);
142 : : return -ENOMEM;
143 : : }
144 : :
145 : : /**
146 : : * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
147 : : * @ebmap: the ebitmap to import
148 : : * @catmap: the NetLabel category bitmap
149 : : *
150 : : * Description:
151 : : * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
152 : : * Returns zero on success, negative values on error.
153 : : *
154 : : */
155 : 0 : int ebitmap_netlbl_import(struct ebitmap *ebmap,
156 : : struct netlbl_lsm_secattr_catmap *catmap)
157 : : {
158 : : struct ebitmap_node *e_iter = NULL;
159 : : struct ebitmap_node *emap_prev = NULL;
160 : : struct netlbl_lsm_secattr_catmap *c_iter = catmap;
161 : : u32 c_idx, c_pos, e_idx, e_sft;
162 : :
163 : : /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
164 : : * however, it is not always compatible with an array of unsigned long
165 : : * in ebitmap_node.
166 : : * In addition, you should pay attention the following implementation
167 : : * assumes unsigned long has a width equal with or less than 64-bit.
168 : : */
169 : :
170 : : do {
171 [ # # ]: 0 : for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) {
172 : : unsigned int delta;
173 : 0 : u64 map = c_iter->bitmap[c_idx];
174 : :
175 [ # # ]: 0 : if (!map)
176 : 0 : continue;
177 : :
178 : 0 : c_pos = c_iter->startbit
179 : 0 : + c_idx * NETLBL_CATMAP_MAPSIZE;
180 [ # # ]: 0 : if (!e_iter
181 [ # # ]: 0 : || c_pos >= e_iter->startbit + EBITMAP_SIZE) {
182 : : e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
183 [ # # ]: 0 : if (!e_iter)
184 : : goto netlbl_import_failure;
185 : : e_iter->startbit
186 : 0 : = c_pos - (c_pos % EBITMAP_SIZE);
187 [ # # ]: 0 : if (emap_prev == NULL)
188 : 0 : ebmap->node = e_iter;
189 : : else
190 : 0 : emap_prev->next = e_iter;
191 : : emap_prev = e_iter;
192 : : }
193 : 0 : delta = c_pos - e_iter->startbit;
194 : 0 : e_idx = delta / EBITMAP_UNIT_SIZE;
195 : : e_sft = delta % EBITMAP_UNIT_SIZE;
196 [ # # ]: 0 : while (map) {
197 : 0 : e_iter->maps[e_idx++] |= map & (-1UL);
198 : 0 : map = EBITMAP_SHIFT_UNIT_SIZE(map);
199 : : }
200 : : }
201 : 0 : c_iter = c_iter->next;
202 [ # # ]: 0 : } while (c_iter);
203 [ # # ]: 0 : if (e_iter != NULL)
204 : 0 : ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
205 : : else
206 : 0 : ebitmap_destroy(ebmap);
207 : :
208 : : return 0;
209 : :
210 : : netlbl_import_failure:
211 : 0 : ebitmap_destroy(ebmap);
212 : 0 : return -ENOMEM;
213 : : }
214 : : #endif /* CONFIG_NETLABEL */
215 : :
216 : : /*
217 : : * Check to see if all the bits set in e2 are also set in e1. Optionally,
218 : : * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed
219 : : * last_e2bit.
220 : : */
221 : 0 : int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit)
222 : : {
223 : : struct ebitmap_node *n1, *n2;
224 : : int i;
225 : :
226 [ # # ]: 0 : if (e1->highbit < e2->highbit)
227 : : return 0;
228 : :
229 : 0 : n1 = e1->node;
230 : 0 : n2 = e2->node;
231 : :
232 [ # # ][ # # ]: 0 : while (n1 && n2 && (n1->startbit <= n2->startbit)) {
233 [ # # ]: 0 : if (n1->startbit < n2->startbit) {
234 : 0 : n1 = n1->next;
235 : 0 : continue;
236 : : }
237 [ # # ][ # # ]: 0 : for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; )
238 : 0 : i--; /* Skip trailing NULL map entries */
239 [ # # ]: 0 : if (last_e2bit && (i >= 0)) {
240 : 0 : u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE +
241 : 0 : __fls(n2->maps[i]);
242 [ # # ]: 0 : if (lastsetbit > last_e2bit)
243 : : return 0;
244 : : }
245 : :
246 [ # # ]: 0 : while (i >= 0) {
247 [ # # ]: 0 : if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
248 : : return 0;
249 : 0 : i--;
250 : : }
251 : :
252 : 0 : n1 = n1->next;
253 : 0 : n2 = n2->next;
254 : : }
255 : :
256 [ # # ]: 0 : if (n2)
257 : : return 0;
258 : :
259 : 0 : return 1;
260 : : }
261 : :
262 : 0 : int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
263 : : {
264 : : struct ebitmap_node *n;
265 : :
266 [ # # ]: 0 : if (e->highbit < bit)
267 : : return 0;
268 : :
269 : 0 : n = e->node;
270 [ # # ][ # # ]: 0 : while (n && (n->startbit <= bit)) {
271 [ # # ]: 0 : if ((n->startbit + EBITMAP_SIZE) > bit)
272 : 0 : return ebitmap_node_get_bit(n, bit);
273 : 0 : n = n->next;
274 : : }
275 : :
276 : : return 0;
277 : : }
278 : :
279 : 0 : int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
280 : : {
281 : : struct ebitmap_node *n, *prev, *new;
282 : :
283 : : prev = NULL;
284 : 0 : n = e->node;
285 [ # # ][ # # ]: 0 : while (n && n->startbit <= bit) {
286 [ # # ]: 0 : if ((n->startbit + EBITMAP_SIZE) > bit) {
287 [ # # ]: 0 : if (value) {
288 : : ebitmap_node_set_bit(n, bit);
289 : : } else {
290 : : unsigned int s;
291 : :
292 : : ebitmap_node_clr_bit(n, bit);
293 : :
294 : 0 : s = find_first_bit(n->maps, EBITMAP_SIZE);
295 [ # # ]: 0 : if (s < EBITMAP_SIZE)
296 : : return 0;
297 : :
298 : : /* drop this node from the bitmap */
299 [ # # ]: 0 : if (!n->next) {
300 : : /*
301 : : * this was the highest map
302 : : * within the bitmap
303 : : */
304 [ # # ]: 0 : if (prev)
305 : 0 : e->highbit = prev->startbit
306 : 0 : + EBITMAP_SIZE;
307 : : else
308 : 0 : e->highbit = 0;
309 : : }
310 [ # # ]: 0 : if (prev)
311 : 0 : prev->next = n->next;
312 : : else
313 : 0 : e->node = n->next;
314 : 0 : kfree(n);
315 : : }
316 : : return 0;
317 : : }
318 : : prev = n;
319 : 0 : n = n->next;
320 : : }
321 : :
322 [ # # ]: 0 : if (!value)
323 : : return 0;
324 : :
325 : : new = kzalloc(sizeof(*new), GFP_ATOMIC);
326 [ # # ]: 0 : if (!new)
327 : : return -ENOMEM;
328 : :
329 : 0 : new->startbit = bit - (bit % EBITMAP_SIZE);
330 : : ebitmap_node_set_bit(new, bit);
331 : :
332 [ # # ]: 0 : if (!n)
333 : : /* this node will be the highest map within the bitmap */
334 : 0 : e->highbit = new->startbit + EBITMAP_SIZE;
335 : :
336 [ # # ]: 0 : if (prev) {
337 : 0 : new->next = prev->next;
338 : 0 : prev->next = new;
339 : : } else {
340 : 0 : new->next = e->node;
341 : 0 : e->node = new;
342 : : }
343 : :
344 : : return 0;
345 : : }
346 : :
347 : 0 : void ebitmap_destroy(struct ebitmap *e)
348 : : {
349 : : struct ebitmap_node *n, *temp;
350 : :
351 [ # # ]: 0 : if (!e)
352 : : return;
353 : :
354 : 0 : n = e->node;
355 [ # # ]: 0 : while (n) {
356 : : temp = n;
357 : 0 : n = n->next;
358 : 0 : kfree(temp);
359 : : }
360 : :
361 : 0 : e->highbit = 0;
362 : 0 : e->node = NULL;
363 : 0 : return;
364 : : }
365 : :
366 : 0 : int ebitmap_read(struct ebitmap *e, void *fp)
367 : : {
368 : : struct ebitmap_node *n = NULL;
369 : : u32 mapunit, count, startbit, index;
370 : : u64 map;
371 : : __le32 buf[3];
372 : : int rc, i;
373 : :
374 : : ebitmap_init(e);
375 : :
376 : : rc = next_entry(buf, fp, sizeof buf);
377 [ # # ]: 0 : if (rc < 0)
378 : : goto out;
379 : :
380 : 0 : mapunit = le32_to_cpu(buf[0]);
381 : 0 : e->highbit = le32_to_cpu(buf[1]);
382 : 0 : count = le32_to_cpu(buf[2]);
383 : :
384 [ # # ]: 0 : if (mapunit != BITS_PER_U64) {
385 : 0 : printk(KERN_ERR "SELinux: ebitmap: map size %u does not "
386 : : "match my size %Zd (high bit was %d)\n",
387 : : mapunit, BITS_PER_U64, e->highbit);
388 : 0 : goto bad;
389 : : }
390 : :
391 : : /* round up e->highbit */
392 : 0 : e->highbit += EBITMAP_SIZE - 1;
393 : 0 : e->highbit -= (e->highbit % EBITMAP_SIZE);
394 : :
395 [ # # ]: 0 : if (!e->highbit) {
396 : 0 : e->node = NULL;
397 : 0 : goto ok;
398 : : }
399 : :
400 [ # # ]: 0 : for (i = 0; i < count; i++) {
401 : : rc = next_entry(&startbit, fp, sizeof(u32));
402 [ # # ]: 0 : if (rc < 0) {
403 : 0 : printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
404 : 0 : goto bad;
405 : : }
406 : 0 : startbit = le32_to_cpu(startbit);
407 : :
408 [ # # ]: 0 : if (startbit & (mapunit - 1)) {
409 : 0 : printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
410 : : "not a multiple of the map unit size (%u)\n",
411 : : startbit, mapunit);
412 : 0 : goto bad;
413 : : }
414 [ # # ]: 0 : if (startbit > e->highbit - mapunit) {
415 : 0 : printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
416 : : "beyond the end of the bitmap (%u)\n",
417 : : startbit, (e->highbit - mapunit));
418 : 0 : goto bad;
419 : : }
420 : :
421 [ # # ][ # # ]: 0 : if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
422 : : struct ebitmap_node *tmp;
423 : : tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
424 [ # # ]: 0 : if (!tmp) {
425 : 0 : printk(KERN_ERR
426 : : "SELinux: ebitmap: out of memory\n");
427 : : rc = -ENOMEM;
428 : 0 : goto bad;
429 : : }
430 : : /* round down */
431 : 0 : tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
432 [ # # ]: 0 : if (n)
433 : 0 : n->next = tmp;
434 : : else
435 : 0 : e->node = tmp;
436 : : n = tmp;
437 [ # # ]: 0 : } else if (startbit <= n->startbit) {
438 : 0 : printk(KERN_ERR "SELinux: ebitmap: start bit %d"
439 : : " comes after start bit %d\n",
440 : : startbit, n->startbit);
441 : 0 : goto bad;
442 : : }
443 : :
444 : : rc = next_entry(&map, fp, sizeof(u64));
445 [ # # ]: 0 : if (rc < 0) {
446 : 0 : printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
447 : 0 : goto bad;
448 : : }
449 : : map = le64_to_cpu(map);
450 : :
451 : 0 : index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
452 [ # # ]: 0 : while (map) {
453 : 0 : n->maps[index++] = map & (-1UL);
454 : 0 : map = EBITMAP_SHIFT_UNIT_SIZE(map);
455 : : }
456 : : }
457 : : ok:
458 : : rc = 0;
459 : : out:
460 : 0 : return rc;
461 : : bad:
462 [ # # ]: 0 : if (!rc)
463 : : rc = -EINVAL;
464 : 0 : ebitmap_destroy(e);
465 : 0 : goto out;
466 : : }
467 : :
468 : 0 : int ebitmap_write(struct ebitmap *e, void *fp)
469 : : {
470 : : struct ebitmap_node *n;
471 : : u32 count;
472 : : __le32 buf[3];
473 : : u64 map;
474 : : int bit, last_bit, last_startbit, rc;
475 : :
476 : 0 : buf[0] = cpu_to_le32(BITS_PER_U64);
477 : :
478 : : count = 0;
479 : : last_bit = 0;
480 : : last_startbit = -1;
481 [ # # ]: 0 : ebitmap_for_each_positive_bit(e, n, bit) {
482 [ # # ]: 0 : if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
483 : 0 : count++;
484 : 0 : last_startbit = rounddown(bit, BITS_PER_U64);
485 : : }
486 : 0 : last_bit = roundup(bit + 1, BITS_PER_U64);
487 : : }
488 : 0 : buf[1] = cpu_to_le32(last_bit);
489 : 0 : buf[2] = cpu_to_le32(count);
490 : :
491 : : rc = put_entry(buf, sizeof(u32), 3, fp);
492 : : if (rc)
493 : : return rc;
494 : :
495 : : map = 0;
496 : : last_startbit = INT_MIN;
497 [ # # ]: 0 : ebitmap_for_each_positive_bit(e, n, bit) {
498 [ # # ]: 0 : if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) {
499 : : __le64 buf64[1];
500 : :
501 : : /* this is the very first bit */
502 [ # # ]: 0 : if (!map) {
503 : 0 : last_startbit = rounddown(bit, BITS_PER_U64);
504 : 0 : map = (u64)1 << (bit - last_startbit);
505 : 0 : continue;
506 : : }
507 : :
508 : : /* write the last node */
509 : 0 : buf[0] = cpu_to_le32(last_startbit);
510 : : rc = put_entry(buf, sizeof(u32), 1, fp);
511 : : if (rc)
512 : : return rc;
513 : :
514 : 0 : buf64[0] = cpu_to_le64(map);
515 : : rc = put_entry(buf64, sizeof(u64), 1, fp);
516 : : if (rc)
517 : : return rc;
518 : :
519 : : /* set up for the next node */
520 : : map = 0;
521 : 0 : last_startbit = rounddown(bit, BITS_PER_U64);
522 : : }
523 : 0 : map |= (u64)1 << (bit - last_startbit);
524 : : }
525 : : /* write the last node */
526 [ # # ]: 0 : if (map) {
527 : : __le64 buf64[1];
528 : :
529 : : /* write the last node */
530 : 0 : buf[0] = cpu_to_le32(last_startbit);
531 : : rc = put_entry(buf, sizeof(u32), 1, fp);
532 : : if (rc)
533 : : return rc;
534 : :
535 : 0 : buf64[0] = cpu_to_le64(map);
536 : : rc = put_entry(buf64, sizeof(u64), 1, fp);
537 : : if (rc)
538 : : return rc;
539 : : }
540 : : return 0;
541 : : }
|
