]>
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 | ||
156 | if (e_iter == NULL || | |
157 | offset >= e_iter->startbit + EBITMAP_SIZE) { | |
158 | e_prev = e_iter; | |
159 | e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC); | |
160 | if (e_iter == NULL) | |
161 | goto netlbl_import_failure; | |
162 | e_iter->startbit = offset & ~(EBITMAP_SIZE - 1); | |
163 | if (e_prev == NULL) | |
164 | ebmap->node = e_iter; | |
165 | else | |
166 | e_prev->next = e_iter; | |
167 | ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; | |
02752760 | 168 | } |
7420ed23 | 169 | |
4b8feff2 PM |
170 | /* offset will always be aligned to an unsigned long */ |
171 | idx = EBITMAP_NODE_INDEX(e_iter, offset); | |
172 | e_iter->maps[idx] = bitmap; | |
173 | ||
174 | /* next */ | |
175 | offset += EBITMAP_UNIT_SIZE; | |
176 | } | |
177 | ||
178 | /* NOTE: we should never reach this return */ | |
7420ed23 | 179 | return 0; |
02752760 PM |
180 | |
181 | netlbl_import_failure: | |
182 | ebitmap_destroy(ebmap); | |
183 | return -ENOMEM; | |
7420ed23 | 184 | } |
02752760 | 185 | #endif /* CONFIG_NETLABEL */ |
7420ed23 | 186 | |
fee71142 WL |
187 | /* |
188 | * Check to see if all the bits set in e2 are also set in e1. Optionally, | |
189 | * if last_e2bit is non-zero, the highest set bit in e2 cannot exceed | |
190 | * last_e2bit. | |
191 | */ | |
192 | int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit) | |
1da177e4 LT |
193 | { |
194 | struct ebitmap_node *n1, *n2; | |
9fe79ad1 | 195 | int i; |
1da177e4 LT |
196 | |
197 | if (e1->highbit < e2->highbit) | |
198 | return 0; | |
199 | ||
200 | n1 = e1->node; | |
201 | n2 = e2->node; | |
fee71142 | 202 | |
1da177e4 LT |
203 | while (n1 && n2 && (n1->startbit <= n2->startbit)) { |
204 | if (n1->startbit < n2->startbit) { | |
205 | n1 = n1->next; | |
206 | continue; | |
207 | } | |
fee71142 WL |
208 | for (i = EBITMAP_UNIT_NUMS - 1; (i >= 0) && !n2->maps[i]; ) |
209 | i--; /* Skip trailing NULL map entries */ | |
210 | if (last_e2bit && (i >= 0)) { | |
211 | u32 lastsetbit = n2->startbit + i * EBITMAP_UNIT_SIZE + | |
212 | __fls(n2->maps[i]); | |
213 | if (lastsetbit > last_e2bit) | |
214 | return 0; | |
215 | } | |
216 | ||
217 | while (i >= 0) { | |
9fe79ad1 KK |
218 | if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) |
219 | return 0; | |
fee71142 | 220 | i--; |
9fe79ad1 | 221 | } |
1da177e4 LT |
222 | |
223 | n1 = n1->next; | |
224 | n2 = n2->next; | |
225 | } | |
226 | ||
227 | if (n2) | |
228 | return 0; | |
229 | ||
230 | return 1; | |
231 | } | |
232 | ||
233 | int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) | |
234 | { | |
235 | struct ebitmap_node *n; | |
236 | ||
237 | if (e->highbit < bit) | |
238 | return 0; | |
239 | ||
240 | n = e->node; | |
241 | while (n && (n->startbit <= bit)) { | |
9fe79ad1 KK |
242 | if ((n->startbit + EBITMAP_SIZE) > bit) |
243 | return ebitmap_node_get_bit(n, bit); | |
1da177e4 LT |
244 | n = n->next; |
245 | } | |
246 | ||
247 | return 0; | |
248 | } | |
249 | ||
250 | int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) | |
251 | { | |
252 | struct ebitmap_node *n, *prev, *new; | |
253 | ||
254 | prev = NULL; | |
255 | n = e->node; | |
256 | while (n && n->startbit <= bit) { | |
9fe79ad1 | 257 | if ((n->startbit + EBITMAP_SIZE) > bit) { |
1da177e4 | 258 | if (value) { |
9fe79ad1 | 259 | ebitmap_node_set_bit(n, bit); |
1da177e4 | 260 | } else { |
9fe79ad1 KK |
261 | unsigned int s; |
262 | ||
263 | ebitmap_node_clr_bit(n, bit); | |
264 | ||
265 | s = find_first_bit(n->maps, EBITMAP_SIZE); | |
266 | if (s < EBITMAP_SIZE) | |
267 | return 0; | |
268 | ||
269 | /* drop this node from the bitmap */ | |
270 | if (!n->next) { | |
271 | /* | |
272 | * this was the highest map | |
273 | * within the bitmap | |
274 | */ | |
1da177e4 | 275 | if (prev) |
9fe79ad1 KK |
276 | e->highbit = prev->startbit |
277 | + EBITMAP_SIZE; | |
1da177e4 | 278 | else |
9fe79ad1 | 279 | e->highbit = 0; |
1da177e4 | 280 | } |
9fe79ad1 KK |
281 | if (prev) |
282 | prev->next = n->next; | |
283 | else | |
284 | e->node = n->next; | |
285 | kfree(n); | |
1da177e4 LT |
286 | } |
287 | return 0; | |
288 | } | |
289 | prev = n; | |
290 | n = n->next; | |
291 | } | |
292 | ||
293 | if (!value) | |
294 | return 0; | |
295 | ||
89d155ef | 296 | new = kzalloc(sizeof(*new), GFP_ATOMIC); |
1da177e4 LT |
297 | if (!new) |
298 | return -ENOMEM; | |
1da177e4 | 299 | |
9fe79ad1 KK |
300 | new->startbit = bit - (bit % EBITMAP_SIZE); |
301 | ebitmap_node_set_bit(new, bit); | |
1da177e4 LT |
302 | |
303 | if (!n) | |
304 | /* this node will be the highest map within the bitmap */ | |
9fe79ad1 | 305 | e->highbit = new->startbit + EBITMAP_SIZE; |
1da177e4 LT |
306 | |
307 | if (prev) { | |
308 | new->next = prev->next; | |
309 | prev->next = new; | |
310 | } else { | |
311 | new->next = e->node; | |
312 | e->node = new; | |
313 | } | |
314 | ||
315 | return 0; | |
316 | } | |
317 | ||
318 | void ebitmap_destroy(struct ebitmap *e) | |
319 | { | |
320 | struct ebitmap_node *n, *temp; | |
321 | ||
322 | if (!e) | |
323 | return; | |
324 | ||
325 | n = e->node; | |
326 | while (n) { | |
327 | temp = n; | |
328 | n = n->next; | |
329 | kfree(temp); | |
330 | } | |
331 | ||
332 | e->highbit = 0; | |
333 | e->node = NULL; | |
334 | return; | |
335 | } | |
336 | ||
337 | int ebitmap_read(struct ebitmap *e, void *fp) | |
338 | { | |
9fe79ad1 KK |
339 | struct ebitmap_node *n = NULL; |
340 | u32 mapunit, count, startbit, index; | |
341 | u64 map; | |
b5bf6c55 | 342 | __le32 buf[3]; |
9fe79ad1 | 343 | int rc, i; |
1da177e4 LT |
344 | |
345 | ebitmap_init(e); | |
346 | ||
347 | rc = next_entry(buf, fp, sizeof buf); | |
348 | if (rc < 0) | |
349 | goto out; | |
350 | ||
9fe79ad1 | 351 | mapunit = le32_to_cpu(buf[0]); |
1da177e4 LT |
352 | e->highbit = le32_to_cpu(buf[1]); |
353 | count = le32_to_cpu(buf[2]); | |
354 | ||
cee74f47 | 355 | if (mapunit != BITS_PER_U64) { |
454d972c | 356 | printk(KERN_ERR "SELinux: ebitmap: map size %u does not " |
9fe79ad1 | 357 | "match my size %Zd (high bit was %d)\n", |
cee74f47 | 358 | mapunit, BITS_PER_U64, e->highbit); |
1da177e4 LT |
359 | goto bad; |
360 | } | |
9fe79ad1 KK |
361 | |
362 | /* round up e->highbit */ | |
363 | e->highbit += EBITMAP_SIZE - 1; | |
364 | e->highbit -= (e->highbit % EBITMAP_SIZE); | |
365 | ||
1da177e4 LT |
366 | if (!e->highbit) { |
367 | e->node = NULL; | |
368 | goto ok; | |
369 | } | |
9fe79ad1 | 370 | |
1da177e4 | 371 | for (i = 0; i < count; i++) { |
9fe79ad1 | 372 | rc = next_entry(&startbit, fp, sizeof(u32)); |
1da177e4 | 373 | if (rc < 0) { |
454d972c | 374 | printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); |
1da177e4 LT |
375 | goto bad; |
376 | } | |
9fe79ad1 | 377 | startbit = le32_to_cpu(startbit); |
1da177e4 | 378 | |
9fe79ad1 | 379 | if (startbit & (mapunit - 1)) { |
454d972c | 380 | printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " |
087feb98 | 381 | "not a multiple of the map unit size (%u)\n", |
9fe79ad1 KK |
382 | startbit, mapunit); |
383 | goto bad; | |
1da177e4 | 384 | } |
9fe79ad1 | 385 | if (startbit > e->highbit - mapunit) { |
454d972c | 386 | printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " |
087feb98 | 387 | "beyond the end of the bitmap (%u)\n", |
9fe79ad1 KK |
388 | startbit, (e->highbit - mapunit)); |
389 | goto bad; | |
390 | } | |
391 | ||
392 | if (!n || startbit >= n->startbit + EBITMAP_SIZE) { | |
393 | struct ebitmap_node *tmp; | |
394 | tmp = kzalloc(sizeof(*tmp), GFP_KERNEL); | |
395 | if (!tmp) { | |
396 | printk(KERN_ERR | |
454d972c | 397 | "SELinux: ebitmap: out of memory\n"); |
9fe79ad1 KK |
398 | rc = -ENOMEM; |
399 | goto bad; | |
400 | } | |
401 | /* round down */ | |
402 | tmp->startbit = startbit - (startbit % EBITMAP_SIZE); | |
7696ee80 | 403 | if (n) |
9fe79ad1 | 404 | n->next = tmp; |
7696ee80 | 405 | else |
9fe79ad1 | 406 | e->node = tmp; |
9fe79ad1 KK |
407 | n = tmp; |
408 | } else if (startbit <= n->startbit) { | |
454d972c | 409 | printk(KERN_ERR "SELinux: ebitmap: start bit %d" |
9fe79ad1 KK |
410 | " comes after start bit %d\n", |
411 | startbit, n->startbit); | |
412 | goto bad; | |
1da177e4 | 413 | } |
9fe79ad1 | 414 | |
1da177e4 LT |
415 | rc = next_entry(&map, fp, sizeof(u64)); |
416 | if (rc < 0) { | |
454d972c | 417 | printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); |
9fe79ad1 | 418 | goto bad; |
1da177e4 | 419 | } |
9fe79ad1 | 420 | map = le64_to_cpu(map); |
1da177e4 | 421 | |
9fe79ad1 KK |
422 | index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; |
423 | while (map) { | |
087feb98 KK |
424 | n->maps[index++] = map & (-1UL); |
425 | map = EBITMAP_SHIFT_UNIT_SIZE(map); | |
1da177e4 | 426 | } |
1da177e4 | 427 | } |
1da177e4 LT |
428 | ok: |
429 | rc = 0; | |
430 | out: | |
431 | return rc; | |
1da177e4 LT |
432 | bad: |
433 | if (!rc) | |
434 | rc = -EINVAL; | |
435 | ebitmap_destroy(e); | |
436 | goto out; | |
437 | } | |
cee74f47 EP |
438 | |
439 | int ebitmap_write(struct ebitmap *e, void *fp) | |
440 | { | |
441 | struct ebitmap_node *n; | |
442 | u32 count; | |
443 | __le32 buf[3]; | |
444 | u64 map; | |
445 | int bit, last_bit, last_startbit, rc; | |
446 | ||
447 | buf[0] = cpu_to_le32(BITS_PER_U64); | |
448 | ||
449 | count = 0; | |
450 | last_bit = 0; | |
451 | last_startbit = -1; | |
452 | ebitmap_for_each_positive_bit(e, n, bit) { | |
453 | if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { | |
454 | count++; | |
455 | last_startbit = rounddown(bit, BITS_PER_U64); | |
456 | } | |
457 | last_bit = roundup(bit + 1, BITS_PER_U64); | |
458 | } | |
459 | buf[1] = cpu_to_le32(last_bit); | |
460 | buf[2] = cpu_to_le32(count); | |
461 | ||
462 | rc = put_entry(buf, sizeof(u32), 3, fp); | |
463 | if (rc) | |
464 | return rc; | |
465 | ||
466 | map = 0; | |
467 | last_startbit = INT_MIN; | |
468 | ebitmap_for_each_positive_bit(e, n, bit) { | |
469 | if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { | |
470 | __le64 buf64[1]; | |
471 | ||
472 | /* this is the very first bit */ | |
473 | if (!map) { | |
474 | last_startbit = rounddown(bit, BITS_PER_U64); | |
475 | map = (u64)1 << (bit - last_startbit); | |
476 | continue; | |
477 | } | |
478 | ||
479 | /* write the last node */ | |
480 | buf[0] = cpu_to_le32(last_startbit); | |
481 | rc = put_entry(buf, sizeof(u32), 1, fp); | |
482 | if (rc) | |
483 | return rc; | |
484 | ||
485 | buf64[0] = cpu_to_le64(map); | |
486 | rc = put_entry(buf64, sizeof(u64), 1, fp); | |
487 | if (rc) | |
488 | return rc; | |
489 | ||
490 | /* set up for the next node */ | |
491 | map = 0; | |
492 | last_startbit = rounddown(bit, BITS_PER_U64); | |
493 | } | |
494 | map |= (u64)1 << (bit - last_startbit); | |
495 | } | |
496 | /* write the last node */ | |
497 | if (map) { | |
498 | __le64 buf64[1]; | |
499 | ||
500 | /* write the last node */ | |
501 | buf[0] = cpu_to_le32(last_startbit); | |
502 | rc = put_entry(buf, sizeof(u32), 1, fp); | |
503 | if (rc) | |
504 | return rc; | |
505 | ||
506 | buf64[0] = cpu_to_le64(map); | |
507 | rc = put_entry(buf64, sizeof(u64), 1, fp); | |
508 | if (rc) | |
509 | return rc; | |
510 | } | |
511 | return 0; | |
512 | } |