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