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