Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/hskinnemoen...
[linux-2.6] / 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.moore@hp.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 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
26 {
27         struct ebitmap_node *n1, *n2;
28
29         if (e1->highbit != e2->highbit)
30                 return 0;
31
32         n1 = e1->node;
33         n2 = e2->node;
34         while (n1 && n2 &&
35                (n1->startbit == n2->startbit) &&
36                !memcmp(n1->maps, n2->maps, EBITMAP_SIZE / 8)) {
37                 n1 = n1->next;
38                 n2 = n2->next;
39         }
40
41         if (n1 || n2)
42                 return 0;
43
44         return 1;
45 }
46
47 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
48 {
49         struct ebitmap_node *n, *new, *prev;
50
51         ebitmap_init(dst);
52         n = src->node;
53         prev = NULL;
54         while (n) {
55                 new = kzalloc(sizeof(*new), GFP_ATOMIC);
56                 if (!new) {
57                         ebitmap_destroy(dst);
58                         return -ENOMEM;
59                 }
60                 new->startbit = n->startbit;
61                 memcpy(new->maps, n->maps, EBITMAP_SIZE / 8);
62                 new->next = NULL;
63                 if (prev)
64                         prev->next = new;
65                 else
66                         dst->node = new;
67                 prev = new;
68                 n = n->next;
69         }
70
71         dst->highbit = src->highbit;
72         return 0;
73 }
74
75 #ifdef CONFIG_NETLABEL
76 /**
77  * ebitmap_netlbl_export - Export an ebitmap into a NetLabel category bitmap
78  * @ebmap: the ebitmap to export
79  * @catmap: the NetLabel category bitmap
80  *
81  * Description:
82  * Export a SELinux extensibile bitmap into a NetLabel category bitmap.
83  * Returns zero on success, negative values on error.
84  *
85  */
86 int ebitmap_netlbl_export(struct ebitmap *ebmap,
87                           struct netlbl_lsm_secattr_catmap **catmap)
88 {
89         struct ebitmap_node *e_iter = ebmap->node;
90         struct netlbl_lsm_secattr_catmap *c_iter;
91         u32 cmap_idx, cmap_sft;
92         int i;
93
94         /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
95          * however, it is not always compatible with an array of unsigned long
96          * in ebitmap_node.
97          * In addition, you should pay attention the following implementation
98          * assumes unsigned long has a width equal with or less than 64-bit.
99          */
100
101         if (e_iter == NULL) {
102                 *catmap = NULL;
103                 return 0;
104         }
105
106         c_iter = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
107         if (c_iter == NULL)
108                 return -ENOMEM;
109         *catmap = c_iter;
110         c_iter->startbit = e_iter->startbit & ~(NETLBL_CATMAP_SIZE - 1);
111
112         while (e_iter != NULL) {
113                 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
114                         unsigned int delta, e_startbit, c_endbit;
115
116                         e_startbit = e_iter->startbit + i * EBITMAP_UNIT_SIZE;
117                         c_endbit = c_iter->startbit + NETLBL_CATMAP_SIZE;
118                         if (e_startbit >= c_endbit) {
119                                 c_iter->next
120                                   = netlbl_secattr_catmap_alloc(GFP_ATOMIC);
121                                 if (c_iter->next == NULL)
122                                         goto netlbl_export_failure;
123                                 c_iter = c_iter->next;
124                                 c_iter->startbit
125                                   = e_startbit & ~(NETLBL_CATMAP_SIZE - 1);
126                         }
127                         delta = e_startbit - c_iter->startbit;
128                         cmap_idx = delta / NETLBL_CATMAP_MAPSIZE;
129                         cmap_sft = delta % NETLBL_CATMAP_MAPSIZE;
130                         c_iter->bitmap[cmap_idx]
131                                 |= e_iter->maps[cmap_idx] << cmap_sft;
132                 }
133                 e_iter = e_iter->next;
134         }
135
136         return 0;
137
138 netlbl_export_failure:
139         netlbl_secattr_catmap_free(*catmap);
140         return -ENOMEM;
141 }
142
143 /**
144  * ebitmap_netlbl_import - Import a NetLabel category bitmap into an ebitmap
145  * @ebmap: the ebitmap to import
146  * @catmap: the NetLabel category bitmap
147  *
148  * Description:
149  * Import a NetLabel category bitmap into a SELinux extensibile bitmap.
150  * Returns zero on success, negative values on error.
151  *
152  */
153 int ebitmap_netlbl_import(struct ebitmap *ebmap,
154                           struct netlbl_lsm_secattr_catmap *catmap)
155 {
156         struct ebitmap_node *e_iter = NULL;
157         struct ebitmap_node *emap_prev = NULL;
158         struct netlbl_lsm_secattr_catmap *c_iter = catmap;
159         u32 c_idx, c_pos, e_idx, e_sft;
160
161         /* NetLabel's NETLBL_CATMAP_MAPTYPE is defined as an array of u64,
162          * however, it is not always compatible with an array of unsigned long
163          * in ebitmap_node.
164          * In addition, you should pay attention the following implementation
165          * assumes unsigned long has a width equal with or less than 64-bit.
166          */
167
168         do {
169                 for (c_idx = 0; c_idx < NETLBL_CATMAP_MAPCNT; c_idx++) {
170                         unsigned int delta;
171                         u64 map = c_iter->bitmap[c_idx];
172
173                         if (!map)
174                                 continue;
175
176                         c_pos = c_iter->startbit
177                                 + c_idx * NETLBL_CATMAP_MAPSIZE;
178                         if (!e_iter
179                             || c_pos >= e_iter->startbit + EBITMAP_SIZE) {
180                                 e_iter = kzalloc(sizeof(*e_iter), GFP_ATOMIC);
181                                 if (!e_iter)
182                                         goto netlbl_import_failure;
183                                 e_iter->startbit
184                                         = c_pos - (c_pos % EBITMAP_SIZE);
185                                 if (emap_prev == NULL)
186                                         ebmap->node = e_iter;
187                                 else
188                                         emap_prev->next = e_iter;
189                                 emap_prev = e_iter;
190                         }
191                         delta = c_pos - e_iter->startbit;
192                         e_idx = delta / EBITMAP_UNIT_SIZE;
193                         e_sft = delta % EBITMAP_UNIT_SIZE;
194                         while (map) {
195                                 e_iter->maps[e_idx++] |= map & (-1UL);
196                                 map = EBITMAP_SHIFT_UNIT_SIZE(map);
197                         }
198                 }
199                 c_iter = c_iter->next;
200         } while (c_iter != NULL);
201         if (e_iter != NULL)
202                 ebmap->highbit = e_iter->startbit + EBITMAP_SIZE;
203         else
204                 ebitmap_destroy(ebmap);
205
206         return 0;
207
208 netlbl_import_failure:
209         ebitmap_destroy(ebmap);
210         return -ENOMEM;
211 }
212 #endif /* CONFIG_NETLABEL */
213
214 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
215 {
216         struct ebitmap_node *n1, *n2;
217         int i;
218
219         if (e1->highbit < e2->highbit)
220                 return 0;
221
222         n1 = e1->node;
223         n2 = e2->node;
224         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
225                 if (n1->startbit < n2->startbit) {
226                         n1 = n1->next;
227                         continue;
228                 }
229                 for (i = 0; i < EBITMAP_UNIT_NUMS; i++) {
230                         if ((n1->maps[i] & n2->maps[i]) != n2->maps[i])
231                                 return 0;
232                 }
233
234                 n1 = n1->next;
235                 n2 = n2->next;
236         }
237
238         if (n2)
239                 return 0;
240
241         return 1;
242 }
243
244 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
245 {
246         struct ebitmap_node *n;
247
248         if (e->highbit < bit)
249                 return 0;
250
251         n = e->node;
252         while (n && (n->startbit <= bit)) {
253                 if ((n->startbit + EBITMAP_SIZE) > bit)
254                         return ebitmap_node_get_bit(n, bit);
255                 n = n->next;
256         }
257
258         return 0;
259 }
260
261 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
262 {
263         struct ebitmap_node *n, *prev, *new;
264
265         prev = NULL;
266         n = e->node;
267         while (n && n->startbit <= bit) {
268                 if ((n->startbit + EBITMAP_SIZE) > bit) {
269                         if (value) {
270                                 ebitmap_node_set_bit(n, bit);
271                         } else {
272                                 unsigned int s;
273
274                                 ebitmap_node_clr_bit(n, bit);
275
276                                 s = find_first_bit(n->maps, EBITMAP_SIZE);
277                                 if (s < EBITMAP_SIZE)
278                                         return 0;
279
280                                 /* drop this node from the bitmap */
281                                 if (!n->next) {
282                                         /*
283                                          * this was the highest map
284                                          * within the bitmap
285                                          */
286                                         if (prev)
287                                                 e->highbit = prev->startbit
288                                                              + EBITMAP_SIZE;
289                                         else
290                                                 e->highbit = 0;
291                                 }
292                                 if (prev)
293                                         prev->next = n->next;
294                                 else
295                                         e->node = n->next;
296                                 kfree(n);
297                         }
298                         return 0;
299                 }
300                 prev = n;
301                 n = n->next;
302         }
303
304         if (!value)
305                 return 0;
306
307         new = kzalloc(sizeof(*new), GFP_ATOMIC);
308         if (!new)
309                 return -ENOMEM;
310
311         new->startbit = bit - (bit % EBITMAP_SIZE);
312         ebitmap_node_set_bit(new, bit);
313
314         if (!n)
315                 /* this node will be the highest map within the bitmap */
316                 e->highbit = new->startbit + EBITMAP_SIZE;
317
318         if (prev) {
319                 new->next = prev->next;
320                 prev->next = new;
321         } else {
322                 new->next = e->node;
323                 e->node = new;
324         }
325
326         return 0;
327 }
328
329 void ebitmap_destroy(struct ebitmap *e)
330 {
331         struct ebitmap_node *n, *temp;
332
333         if (!e)
334                 return;
335
336         n = e->node;
337         while (n) {
338                 temp = n;
339                 n = n->next;
340                 kfree(temp);
341         }
342
343         e->highbit = 0;
344         e->node = NULL;
345         return;
346 }
347
348 int ebitmap_read(struct ebitmap *e, void *fp)
349 {
350         struct ebitmap_node *n = NULL;
351         u32 mapunit, count, startbit, index;
352         u64 map;
353         __le32 buf[3];
354         int rc, i;
355
356         ebitmap_init(e);
357
358         rc = next_entry(buf, fp, sizeof buf);
359         if (rc < 0)
360                 goto out;
361
362         mapunit = le32_to_cpu(buf[0]);
363         e->highbit = le32_to_cpu(buf[1]);
364         count = le32_to_cpu(buf[2]);
365
366         if (mapunit != sizeof(u64) * 8) {
367                 printk(KERN_ERR "SELinux: ebitmap: map size %u does not "
368                        "match my size %Zd (high bit was %d)\n",
369                        mapunit, sizeof(u64) * 8, e->highbit);
370                 goto bad;
371         }
372
373         /* round up e->highbit */
374         e->highbit += EBITMAP_SIZE - 1;
375         e->highbit -= (e->highbit % EBITMAP_SIZE);
376
377         if (!e->highbit) {
378                 e->node = NULL;
379                 goto ok;
380         }
381
382         for (i = 0; i < count; i++) {
383                 rc = next_entry(&startbit, fp, sizeof(u32));
384                 if (rc < 0) {
385                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
386                         goto bad;
387                 }
388                 startbit = le32_to_cpu(startbit);
389
390                 if (startbit & (mapunit - 1)) {
391                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
392                                "not a multiple of the map unit size (%u)\n",
393                                startbit, mapunit);
394                         goto bad;
395                 }
396                 if (startbit > e->highbit - mapunit) {
397                         printk(KERN_ERR "SELinux: ebitmap start bit (%d) is "
398                                "beyond the end of the bitmap (%u)\n",
399                                startbit, (e->highbit - mapunit));
400                         goto bad;
401                 }
402
403                 if (!n || startbit >= n->startbit + EBITMAP_SIZE) {
404                         struct ebitmap_node *tmp;
405                         tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
406                         if (!tmp) {
407                                 printk(KERN_ERR
408                                        "SELinux: ebitmap: out of memory\n");
409                                 rc = -ENOMEM;
410                                 goto bad;
411                         }
412                         /* round down */
413                         tmp->startbit = startbit - (startbit % EBITMAP_SIZE);
414                         if (n) {
415                                 n->next = tmp;
416                         } else {
417                                 e->node = tmp;
418                         }
419                         n = tmp;
420                 } else if (startbit <= n->startbit) {
421                         printk(KERN_ERR "SELinux: ebitmap: start bit %d"
422                                " comes after start bit %d\n",
423                                startbit, n->startbit);
424                         goto bad;
425                 }
426
427                 rc = next_entry(&map, fp, sizeof(u64));
428                 if (rc < 0) {
429                         printk(KERN_ERR "SELinux: ebitmap: truncated map\n");
430                         goto bad;
431                 }
432                 map = le64_to_cpu(map);
433
434                 index = (startbit - n->startbit) / EBITMAP_UNIT_SIZE;
435                 while (map) {
436                         n->maps[index++] = map & (-1UL);
437                         map = EBITMAP_SHIFT_UNIT_SIZE(map);
438                 }
439         }
440 ok:
441         rc = 0;
442 out:
443         return rc;
444 bad:
445         if (!rc)
446                 rc = -EINVAL;
447         ebitmap_destroy(e);
448         goto out;
449 }