GNU Linux-libre 4.9.309-gnu1
[releases.git] / security / selinux / ss / ebitmap.c
1 /*
2  * Implementation of the extensible bitmap type.
3  *
4  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5  */
6 /*
7  * Updated: Hewlett-Packard <paul@paul-moore.com>
8  *
9  *      Added support to import/export the NetLabel category bitmap
10  *
11  * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
12  */
13 /*
14  * Updated: KaiGai Kohei <kaigai@ak.jp.nec.com>
15  *      Applied standard bit operations to improve bitmap scanning.
16  */
17
18 #include <linux/kernel.h>
19 #include <linux/slab.h>
20 #include <linux/errno.h>
21 #include <net/netlabel.h>
22 #include "ebitmap.h"
23 #include "policydb.h"
24
25 #define BITS_PER_U64    (sizeof(u64) * 8)
26
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) &&
38                !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
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) {
57                 new = kzalloc(sizeof(*new), GFP_ATOMIC);
58                 if (!new) {
59                         ebitmap_destroy(dst);
60                         return -ENOMEM;
61                 }
62                 new->startbit = n->startbit;
63                 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
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
77 #ifdef CONFIG_NETLABEL
78 /**
79  * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
80  * @ebmap: the ebitmap to export
81  * @catmap: the NetLabel category bitmap
82  *
83  * Description:
84  * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
85  * Returns zero on success, negative values on error.
86  *
87  */
88 int ebitmap_netlbl_export(struct ebitmap *ebmap,
89                           struct netlbl_lsm_catmap **catmap)
90 {
91         struct ebitmap_node *e_iter = ebmap->node;
92         unsigned long e_map;
93         u32 offset;
94         unsigned int iter;
95         int rc;
96
97         if (e_iter == NULL) {
98                 *catmap = NULL;
99                 return 0;
100         }
101
102         if (*catmap != NULL)
103                 netlbl_catmap_free(*catmap);
104         *catmap = NULL;
105
106         while (e_iter) {
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) {
111                                 rc = netlbl_catmap_setlong(catmap,
112                                                            offset,
113                                                            e_map,
114                                                            GFP_ATOMIC);
115                                 if (rc != 0)
116                                         goto netlbl_export_failure;
117                         }
118                         offset += EBITMAP_UNIT_SIZE;
119                 }
120                 e_iter = e_iter->next;
121         }
122
123         return 0;
124
125 netlbl_export_failure:
126         netlbl_catmap_free(*catmap);
127         return -ENOMEM;
128 }
129
130 /**
131  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
132  * @ebmap: the ebitmap to import
133  * @catmap: the NetLabel category bitmap
134  *
135  * Description:
136  * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
137  * Returns zero on success, negative values on error.
138  *
139  */
140 int ebitmap_netlbl_import(struct ebitmap *ebmap,
141                           struct netlbl_lsm_catmap *catmap)
142 {
143         int rc;
144         struct ebitmap_node *e_iter = NULL;
145         struct ebitmap_node *e_prev = NULL;
146         u32 offset = 0, idx;
147         unsigned long bitmap;
148
149         for (;;) {
150                 rc = netlbl_catmap_getlong(catmap, &offset, &bitmap);
151                 if (rc < 0)
152                         goto netlbl_import_failure;
153                 if (offset == (u32)-1)
154                         return 0;
155
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
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;
168                         e_iter->startbit = offset - (offset % EBITMAP_SIZE);
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;
174                 }
175
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 */
185         return 0;
186
187 netlbl_import_failure:
188         ebitmap_destroy(ebmap);
189         return -ENOMEM;
190 }
191 #endif /* CONFIG_NETLABEL */
192
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)
199 {
200         struct ebitmap_node *n1, *n2;
201         int i;
202
203         if (e1->highbit < e2->highbit)
204                 return 0;
205
206         n1 = e1->node;
207         n2 = e2->node;
208
209         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
210                 if (n1->startbit < n2->startbit) {
211                         n1 = n1->next;
212                         continue;
213                 }
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) {
224                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
225                                 return 0;
226                         i--;
227                 }
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)) {
248                 if ((n->startbit + EBITMAP_SIZE) > bit)
249                         return ebitmap_node_get_bit(n, bit);
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) {
263                 if ((n->startbit + EBITMAP_SIZE) > bit) {
264                         if (value) {
265                                 ebitmap_node_set_bit(n, bit);
266                         } else {
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                                          */
281                                         if (prev)
282                                                 e->highbit = prev->startbit
283                                                              + EBITMAP_SIZE;
284                                         else
285                                                 e->highbit = 0;
286                                 }
287                                 if (prev)
288                                         prev->next = n->next;
289                                 else
290                                         e->node = n->next;
291                                 kfree(n);
292                         }
293                         return 0;
294                 }
295                 prev = n;
296                 n = n->next;
297         }
298
299         if (!value)
300                 return 0;
301
302         new = kzalloc(sizeof(*new), GFP_ATOMIC);
303         if (!new)
304                 return -ENOMEM;
305
306         new->startbit = bit - (bit % EBITMAP_SIZE);
307         ebitmap_node_set_bit(new, bit);
308
309         if (!n)
310                 /* this node will be the highest map within the bitmap */
311                 e->highbit = new->startbit + EBITMAP_SIZE;
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 {
345         struct ebitmap_node *n = NULL;
346         u32 mapunit, count, startbit, index;
347         u64 map;
348         __le32 buf[3];
349         int rc, i;
350
351         ebitmap_init(e);
352
353         rc = next_entry(buf, fp, sizeof buf);
354         if (rc < 0)
355                 goto out;
356
357         mapunit = le32_to_cpu(buf[0]);
358         e->highbit = le32_to_cpu(buf[1]);
359         count = le32_to_cpu(buf[2]);
360
361         if (mapunit != BITS_PER_U64) {
362                 printk(KERN_ERR "SELinux: ebitmap: map size %u does not "
363                        "match my size %Zd (high bit was %d)\n",
364                        mapunit, BITS_PER_U64, e->highbit);
365                 goto bad;
366         }
367
368         /* round up e->highbit */
369         e->highbit += EBITMAP_SIZE - 1;
370         e->highbit -= (e->highbit % EBITMAP_SIZE);
371
372         if (!e->highbit) {
373                 e->node = NULL;
374                 goto ok;
375         }
376
377         if (e->highbit && !count)
378                 goto bad;
379
380         for (i = 0; i < count; i++) {
381                 rc = next_entry(&startbit, fp, sizeof(u32));
382                 if (rc < 0) {
383                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
384                         goto bad;
385                 }
386                 startbit = le32_to_cpu(startbit);
387
388                 if (startbit & (mapunit - 1)) {
389                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
390                                "not a multiple of the map unit size (%u)\n",
391                                startbit, mapunit);
392                         goto bad;
393                 }
394                 if (startbit > e->highbit - mapunit) {
395                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
396                                "beyond the end of the bitmap (%u)\n",
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
406                                        "SELinux: ebitmap: out of memory\n");
407                                 rc = -ENOMEM;
408                                 goto bad;
409                         }
410                         /* round down */
411                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
412                         if (n)
413                                 n->next = tmp;
414                         else
415                                 e->node = tmp;
416                         n = tmp;
417                 } else if (startbit <= n->startbit) {
418                         printk(KERN_ERR "SELinux: ebitmap: start bit %d"
419                                " comes after start bit %d\n",
420                                startbit, n->startbit);
421                         goto bad;
422                 }
423
424                 rc = next_entry(&map, fp, sizeof(u64));
425                 if (rc < 0) {
426                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
427                         goto bad;
428                 }
429                 map = le64_to_cpu(map);
430
431                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
432                 while (map) {
433                         n->maps[index++] = map & (-1UL);
434                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
435                 }
436         }
437 ok:
438         rc = 0;
439 out:
440         return rc;
441 bad:
442         if (!rc)
443                 rc = -EINVAL;
444         ebitmap_destroy(e);
445         goto out;
446 }
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 }