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