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 PM |
88 | int ebitmap_netlbl_export(struct ebitmap *ebmap, |
89 | struct netlbl_lsm_secattr_catmap **catmap) | |
7420ed23 | 90 | { |
02752760 PM |
91 | struct ebitmap_node *e_iter = ebmap->node; |
92 | struct netlbl_lsm_secattr_catmap *c_iter; | |
9fe79ad1 KK |
93 | u32 cmap_idx, cmap_sft; |
94 | int i; | |
02752760 | 95 | |
9fe79ad1 KK |
96 | /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64, |
97 | * however, it is not always compatible with an array of unsigned long | |
98 | * in ebitmap_node. | |
99 | * In addition, you should pay attention the following implementation | |
100 | * assumes unsigned long has a width equal with or less than 64-bit. | |
101 | */ | |
02752760 PM |
102 | |
103 | if (e_iter == NULL) { | |
104 | *catmap = NULL; | |
bf0edf39 PM |
105 | return 0; |
106 | } | |
107 | ||
02752760 PM |
108 | c_iter = netlbl_secattr_catmap_alloc(GFP_ATOMIC); |
109 | if (c_iter == NULL) | |
7420ed23 | 110 | return -ENOMEM; |
02752760 PM |
111 | *catmap = c_iter; |
112 | c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1); | |
113 | ||
dbc74c65 | 114 | while (e_iter) { |
9fe79ad1 KK |
115 | for (i = 0; i < EBITMAP_UNIT_NUMS; i++) { |
116 | unsigned int delta, e_startbit, c_endbit; | |
117 | ||
118 | e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE; | |
119 | c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE; | |
120 | if (e_startbit >= c_endbit) { | |
121 | c_iter->next | |
122 | = netlbl_secattr_catmap_alloc(GFP_ATOMIC); | |
123 | if (c_iter->next == NULL) | |
124 | goto netlbl_export_failure; | |
125 | c_iter = c_iter->next; | |
126 | c_iter->startbit | |
127 | = e_startbit & ~(NETLBL_CATMAP_SIZE - 1); | |
128 | } | |
129 | delta = e_startbit - c_iter->startbit; | |
130 | cmap_idx = delta / NETLBL_CATMAP_MAPSIZE; | |
131 | cmap_sft = delta % NETLBL_CATMAP_MAPSIZE; | |
132 | c_iter->bitmap[cmap_idx] | |
c36f74e6 | 133 | |= e_iter->maps[i] << cmap_sft; |
02752760 | 134 | } |
6d2b6855 | 135 | e_iter = e_iter->next; |
02752760 | 136 | } |
7420ed23 | 137 | |
7420ed23 | 138 | return 0; |
02752760 PM |
139 | |
140 | netlbl_export_failure: | |
141 | netlbl_secattr_catmap_free(*catmap); | |
142 | return -ENOMEM; | |
7420ed23 VY |
143 | } |
144 | ||
145 | /** | |
02752760 | 146 | * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap |
9fe79ad1 | 147 | * @ebmap: the ebitmap to import |
02752760 | 148 | * @catmap: the NetLabel category bitmap |
7420ed23 VY |
149 | * |
150 | * Description: | |
02752760 PM |
151 | * Import a NetLabel category bitmap into a SELinux extensibile bitmap. |
152 | * Returns zero on success, negative values on error. | |
7420ed23 VY |
153 | * |
154 | */ | |
02752760 PM |
155 | int ebitmap_netlbl_import(struct ebitmap *ebmap, |
156 | struct netlbl_lsm_secattr_catmap *catmap) | |
7420ed23 | 157 | { |
02752760 PM |
158 | struct ebitmap_node *e_iter = NULL; |
159 | struct ebitmap_node *emap_prev = NULL; | |
160 | struct netlbl_lsm_secattr_catmap *c_iter = catmap; | |
9fe79ad1 | 161 | u32 c_idx, c_pos, e_idx, e_sft; |
7420ed23 | 162 | |
9fe79ad1 KK |
163 | /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64, |
164 | * however, it is not always compatible with an array of unsigned long | |
165 | * in ebitmap_node. | |
166 | * In addition, you should pay attention the following implementation | |
167 | * assumes unsigned long has a width equal with or less than 64-bit. | |
168 | */ | |
7420ed23 | 169 | |
02752760 PM |
170 | do { |
171 | for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) { | |
9fe79ad1 KK |
172 | unsigned int delta; |
173 | u64 map = c_iter->bitmap[c_idx]; | |
174 | ||
175 | if (!map) | |
02752760 | 176 | continue; |
7420ed23 | 177 | |
9fe79ad1 KK |
178 | c_pos = c_iter->startbit |
179 | + c_idx * NETLBL_CATMAP_MAPSIZE; | |
180 | if (!e_iter | |
181 | || c_pos >= e_iter->startbit + EBITMAP_SIZE) { | |
182 | e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC); | |
183 | if (!e_iter) | |
184 | goto netlbl_import_failure; | |
185 | e_iter->startbit | |
186 | = c_pos - (c_pos % EBITMAP_SIZE); | |
187 | if (emap_prev == NULL) | |
188 | ebmap->node = e_iter; | |
189 | else | |
190 | emap_prev->next = e_iter; | |
191 | emap_prev = e_iter; | |
192 | } | |
193 | delta = c_pos - e_iter->startbit; | |
194 | e_idx = delta / EBITMAP_UNIT_SIZE; | |
195 | e_sft = delta % EBITMAP_UNIT_SIZE; | |
196 | while (map) { | |
197 | e_iter->maps[e_idx++] |= map & (-1UL); | |
087feb98 | 198 | map = EBITMAP_SHIFT_UNIT_SIZE(map); |
9fe79ad1 | 199 | } |
02752760 PM |
200 | } |
201 | c_iter = c_iter->next; | |
dbc74c65 | 202 | } while (c_iter); |
02752760 | 203 | if (e_iter != NULL) |
9fe79ad1 | 204 | ebmap->highbit = e_iter->startbit + EBITMAP_SIZE; |
7420ed23 | 205 | else |
02752760 | 206 | ebitmap_destroy(ebmap); |
7420ed23 VY |
207 | |
208 | return 0; | |
02752760 PM |
209 | |
210 | netlbl_import_failure: | |
211 | ebitmap_destroy(ebmap); | |
212 | return -ENOMEM; | |
7420ed23 | 213 | } |
02752760 | 214 | #endif /* CONFIG_NETLABEL */ |
7420ed23 | 215 | |
1da177e4 LT |
216 | int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2) |
217 | { | |
218 | struct ebitmap_node *n1, *n2; | |
9fe79ad1 | 219 | int i; |
1da177e4 LT |
220 | |
221 | if (e1->highbit < e2->highbit) | |
222 | return 0; | |
223 | ||
224 | n1 = e1->node; | |
225 | n2 = e2->node; | |
226 | while (n1 && n2 && (n1->startbit <= n2->startbit)) { | |
227 | if (n1->startbit < n2->startbit) { | |
228 | n1 = n1->next; | |
229 | continue; | |
230 | } | |
9fe79ad1 KK |
231 | for (i = 0; i < EBITMAP_UNIT_NUMS; i++) { |
232 | if ((n1->maps[i] & n2->maps[i]) != n2->maps[i]) | |
233 | return 0; | |
234 | } | |
1da177e4 LT |
235 | |
236 | n1 = n1->next; | |
237 | n2 = n2->next; | |
238 | } | |
239 | ||
240 | if (n2) | |
241 | return 0; | |
242 | ||
243 | return 1; | |
244 | } | |
245 | ||
246 | int ebitmap_get_bit(struct ebitmap *e, unsigned long bit) | |
247 | { | |
248 | struct ebitmap_node *n; | |
249 | ||
250 | if (e->highbit < bit) | |
251 | return 0; | |
252 | ||
253 | n = e->node; | |
254 | while (n && (n->startbit <= bit)) { | |
9fe79ad1 KK |
255 | if ((n->startbit + EBITMAP_SIZE) > bit) |
256 | return ebitmap_node_get_bit(n, bit); | |
1da177e4 LT |
257 | n = n->next; |
258 | } | |
259 | ||
260 | return 0; | |
261 | } | |
262 | ||
263 | int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value) | |
264 | { | |
265 | struct ebitmap_node *n, *prev, *new; | |
266 | ||
267 | prev = NULL; | |
268 | n = e->node; | |
269 | while (n && n->startbit <= bit) { | |
9fe79ad1 | 270 | if ((n->startbit + EBITMAP_SIZE) > bit) { |
1da177e4 | 271 | if (value) { |
9fe79ad1 | 272 | ebitmap_node_set_bit(n, bit); |
1da177e4 | 273 | } else { |
9fe79ad1 KK |
274 | unsigned int s; |
275 | ||
276 | ebitmap_node_clr_bit(n, bit); | |
277 | ||
278 | s = find_first_bit(n->maps, EBITMAP_SIZE); | |
279 | if (s < EBITMAP_SIZE) | |
280 | return 0; | |
281 | ||
282 | /* drop this node from the bitmap */ | |
283 | if (!n->next) { | |
284 | /* | |
285 | * this was the highest map | |
286 | * within the bitmap | |
287 | */ | |
1da177e4 | 288 | if (prev) |
9fe79ad1 KK |
289 | e->highbit = prev->startbit |
290 | + EBITMAP_SIZE; | |
1da177e4 | 291 | else |
9fe79ad1 | 292 | e->highbit = 0; |
1da177e4 | 293 | } |
9fe79ad1 KK |
294 | if (prev) |
295 | prev->next = n->next; | |
296 | else | |
297 | e->node = n->next; | |
298 | kfree(n); | |
1da177e4 LT |
299 | } |
300 | return 0; | |
301 | } | |
302 | prev = n; | |
303 | n = n->next; | |
304 | } | |
305 | ||
306 | if (!value) | |
307 | return 0; | |
308 | ||
89d155ef | 309 | new = kzalloc(sizeof(*new), GFP_ATOMIC); |
1da177e4 LT |
310 | if (!new) |
311 | return -ENOMEM; | |
1da177e4 | 312 | |
9fe79ad1 KK |
313 | new->startbit = bit - (bit % EBITMAP_SIZE); |
314 | ebitmap_node_set_bit(new, bit); | |
1da177e4 LT |
315 | |
316 | if (!n) | |
317 | /* this node will be the highest map within the bitmap */ | |
9fe79ad1 | 318 | e->highbit = new->startbit + EBITMAP_SIZE; |
1da177e4 LT |
319 | |
320 | if (prev) { | |
321 | new->next = prev->next; | |
322 | prev->next = new; | |
323 | } else { | |
324 | new->next = e->node; | |
325 | e->node = new; | |
326 | } | |
327 | ||
328 | return 0; | |
329 | } | |
330 | ||
331 | void ebitmap_destroy(struct ebitmap *e) | |
332 | { | |
333 | struct ebitmap_node *n, *temp; | |
334 | ||
335 | if (!e) | |
336 | return; | |
337 | ||
338 | n = e->node; | |
339 | while (n) { | |
340 | temp = n; | |
341 | n = n->next; | |
342 | kfree(temp); | |
343 | } | |
344 | ||
345 | e->highbit = 0; | |
346 | e->node = NULL; | |
347 | return; | |
348 | } | |
349 | ||
350 | int ebitmap_read(struct ebitmap *e, void *fp) | |
351 | { | |
9fe79ad1 KK |
352 | struct ebitmap_node *n = NULL; |
353 | u32 mapunit, count, startbit, index; | |
354 | u64 map; | |
b5bf6c55 | 355 | __le32 buf[3]; |
9fe79ad1 | 356 | int rc, i; |
1da177e4 LT |
357 | |
358 | ebitmap_init(e); | |
359 | ||
360 | rc = next_entry(buf, fp, sizeof buf); | |
361 | if (rc < 0) | |
362 | goto out; | |
363 | ||
9fe79ad1 | 364 | mapunit = le32_to_cpu(buf[0]); |
1da177e4 LT |
365 | e->highbit = le32_to_cpu(buf[1]); |
366 | count = le32_to_cpu(buf[2]); | |
367 | ||
cee74f47 | 368 | if (mapunit != BITS_PER_U64) { |
454d972c | 369 | printk(KERN_ERR "SELinux: ebitmap: map size %u does not " |
9fe79ad1 | 370 | "match my size %Zd (high bit was %d)\n", |
cee74f47 | 371 | mapunit, BITS_PER_U64, e->highbit); |
1da177e4 LT |
372 | goto bad; |
373 | } | |
9fe79ad1 KK |
374 | |
375 | /* round up e->highbit */ | |
376 | e->highbit += EBITMAP_SIZE - 1; | |
377 | e->highbit -= (e->highbit % EBITMAP_SIZE); | |
378 | ||
1da177e4 LT |
379 | if (!e->highbit) { |
380 | e->node = NULL; | |
381 | goto ok; | |
382 | } | |
9fe79ad1 | 383 | |
1da177e4 | 384 | for (i = 0; i < count; i++) { |
9fe79ad1 | 385 | rc = next_entry(&startbit, fp, sizeof(u32)); |
1da177e4 | 386 | if (rc < 0) { |
454d972c | 387 | printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); |
1da177e4 LT |
388 | goto bad; |
389 | } | |
9fe79ad1 | 390 | startbit = le32_to_cpu(startbit); |
1da177e4 | 391 | |
9fe79ad1 | 392 | if (startbit & (mapunit - 1)) { |
454d972c | 393 | printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " |
087feb98 | 394 | "not a multiple of the map unit size (%u)\n", |
9fe79ad1 KK |
395 | startbit, mapunit); |
396 | goto bad; | |
1da177e4 | 397 | } |
9fe79ad1 | 398 | if (startbit > e->highbit - mapunit) { |
454d972c | 399 | printk(KERN_ERR "SELinux: ebitmap start bit (%d) is " |
087feb98 | 400 | "beyond the end of the bitmap (%u)\n", |
9fe79ad1 KK |
401 | startbit, (e->highbit - mapunit)); |
402 | goto bad; | |
403 | } | |
404 | ||
405 | if (!n || startbit >= n->startbit + EBITMAP_SIZE) { | |
406 | struct ebitmap_node *tmp; | |
407 | tmp = kzalloc(sizeof(*tmp), GFP_KERNEL); | |
408 | if (!tmp) { | |
409 | printk(KERN_ERR | |
454d972c | 410 | "SELinux: ebitmap: out of memory\n"); |
9fe79ad1 KK |
411 | rc = -ENOMEM; |
412 | goto bad; | |
413 | } | |
414 | /* round down */ | |
415 | tmp->startbit = startbit - (startbit % EBITMAP_SIZE); | |
7696ee80 | 416 | if (n) |
9fe79ad1 | 417 | n->next = tmp; |
7696ee80 | 418 | else |
9fe79ad1 | 419 | e->node = tmp; |
9fe79ad1 KK |
420 | n = tmp; |
421 | } else if (startbit <= n->startbit) { | |
454d972c | 422 | printk(KERN_ERR "SELinux: ebitmap: start bit %d" |
9fe79ad1 KK |
423 | " comes after start bit %d\n", |
424 | startbit, n->startbit); | |
425 | goto bad; | |
1da177e4 | 426 | } |
9fe79ad1 | 427 | |
1da177e4 LT |
428 | rc = next_entry(&map, fp, sizeof(u64)); |
429 | if (rc < 0) { | |
454d972c | 430 | printk(KERN_ERR "SELinux: ebitmap: truncated map\n"); |
9fe79ad1 | 431 | goto bad; |
1da177e4 | 432 | } |
9fe79ad1 | 433 | map = le64_to_cpu(map); |
1da177e4 | 434 | |
9fe79ad1 KK |
435 | index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE; |
436 | while (map) { | |
087feb98 KK |
437 | n->maps[index++] = map & (-1UL); |
438 | map = EBITMAP_SHIFT_UNIT_SIZE(map); | |
1da177e4 | 439 | } |
1da177e4 | 440 | } |
1da177e4 LT |
441 | ok: |
442 | rc = 0; | |
443 | out: | |
444 | return rc; | |
1da177e4 LT |
445 | bad: |
446 | if (!rc) | |
447 | rc = -EINVAL; | |
448 | ebitmap_destroy(e); | |
449 | goto out; | |
450 | } | |
cee74f47 EP |
451 | |
452 | int ebitmap_write(struct ebitmap *e, void *fp) | |
453 | { | |
454 | struct ebitmap_node *n; | |
455 | u32 count; | |
456 | __le32 buf[3]; | |
457 | u64 map; | |
458 | int bit, last_bit, last_startbit, rc; | |
459 | ||
460 | buf[0] = cpu_to_le32(BITS_PER_U64); | |
461 | ||
462 | count = 0; | |
463 | last_bit = 0; | |
464 | last_startbit = -1; | |
465 | ebitmap_for_each_positive_bit(e, n, bit) { | |
466 | if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { | |
467 | count++; | |
468 | last_startbit = rounddown(bit, BITS_PER_U64); | |
469 | } | |
470 | last_bit = roundup(bit + 1, BITS_PER_U64); | |
471 | } | |
472 | buf[1] = cpu_to_le32(last_bit); | |
473 | buf[2] = cpu_to_le32(count); | |
474 | ||
475 | rc = put_entry(buf, sizeof(u32), 3, fp); | |
476 | if (rc) | |
477 | return rc; | |
478 | ||
479 | map = 0; | |
480 | last_startbit = INT_MIN; | |
481 | ebitmap_for_each_positive_bit(e, n, bit) { | |
482 | if (rounddown(bit, (int)BITS_PER_U64) > last_startbit) { | |
483 | __le64 buf64[1]; | |
484 | ||
485 | /* this is the very first bit */ | |
486 | if (!map) { | |
487 | last_startbit = rounddown(bit, BITS_PER_U64); | |
488 | map = (u64)1 << (bit - last_startbit); | |
489 | continue; | |
490 | } | |
491 | ||
492 | /* write the last node */ | |
493 | buf[0] = cpu_to_le32(last_startbit); | |
494 | rc = put_entry(buf, sizeof(u32), 1, fp); | |
495 | if (rc) | |
496 | return rc; | |
497 | ||
498 | buf64[0] = cpu_to_le64(map); | |
499 | rc = put_entry(buf64, sizeof(u64), 1, fp); | |
500 | if (rc) | |
501 | return rc; | |
502 | ||
503 | /* set up for the next node */ | |
504 | map = 0; | |
505 | last_startbit = rounddown(bit, BITS_PER_U64); | |
506 | } | |
507 | map |= (u64)1 << (bit - last_startbit); | |
508 | } | |
509 | /* write the last node */ | |
510 | if (map) { | |
511 | __le64 buf64[1]; | |
512 | ||
513 | /* write the last node */ | |
514 | buf[0] = cpu_to_le32(last_startbit); | |
515 | rc = put_entry(buf, sizeof(u32), 1, fp); | |
516 | if (rc) | |
517 | return rc; | |
518 | ||
519 | buf64[0] = cpu_to_le64(map); | |
520 | rc = put_entry(buf64, sizeof(u64), 1, fp); | |
521 | if (rc) | |
522 | return rc; | |
523 | } | |
524 | return 0; | |
525 | } |