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