Merge branch 'upstream-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/ieee13...
[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 ebitmap_export() and ebitmap_import()
10  *
11  * (c) Copyright Hewlett-Packard Development Company, L.P., 2006
12  */
13
14 #include <linux/kernel.h>
15 #include <linux/slab.h>
16 #include <linux/errno.h>
17 #include "ebitmap.h"
18 #include "policydb.h"
19
20 int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2)
21 {
22         struct ebitmap_node *n1, *n2;
23
24         if (e1->highbit != e2->highbit)
25                 return 0;
26
27         n1 = e1->node;
28         n2 = e2->node;
29         while (n1 && n2 &&
30                (n1->startbit == n2->startbit) &&
31                (n1->map == n2->map)) {
32                 n1 = n1->next;
33                 n2 = n2->next;
34         }
35
36         if (n1 || n2)
37                 return 0;
38
39         return 1;
40 }
41
42 int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src)
43 {
44         struct ebitmap_node *n, *new, *prev;
45
46         ebitmap_init(dst);
47         n = src->node;
48         prev = NULL;
49         while (n) {
50                 new = kzalloc(sizeof(*new), GFP_ATOMIC);
51                 if (!new) {
52                         ebitmap_destroy(dst);
53                         return -ENOMEM;
54                 }
55                 new->startbit = n->startbit;
56                 new->map = n->map;
57                 new->next = NULL;
58                 if (prev)
59                         prev->next = new;
60                 else
61                         dst->node = new;
62                 prev = new;
63                 n = n->next;
64         }
65
66         dst->highbit = src->highbit;
67         return 0;
68 }
69
70 /**
71  * ebitmap_export - Export an ebitmap to a unsigned char bitmap string
72  * @src: the ebitmap to export
73  * @dst: the resulting bitmap string
74  * @dst_len: length of dst in bytes
75  *
76  * Description:
77  * Allocate a buffer at least src->highbit bits long and export the extensible
78  * bitmap into the buffer.  The bitmap string will be in little endian format,
79  * i.e. LSB first.  The value returned in dst_len may not the true size of the
80  * buffer as the length of the buffer is rounded up to a multiple of MAPTYPE.
81  * The caller must free the buffer when finished. Returns zero on success,
82  * negative values on failure.
83  *
84  */
85 int ebitmap_export(const struct ebitmap *src,
86                    unsigned char **dst,
87                    size_t *dst_len)
88 {
89         size_t bitmap_len;
90         unsigned char *bitmap;
91         struct ebitmap_node *iter_node;
92         MAPTYPE node_val;
93         size_t bitmap_byte;
94         unsigned char bitmask;
95
96         bitmap_len = src->highbit / 8;
97         if (src->highbit % 7)
98                 bitmap_len += 1;
99         if (bitmap_len == 0)
100                 return -EINVAL;
101
102         bitmap = kzalloc((bitmap_len & ~(sizeof(MAPTYPE) - 1)) +
103                          sizeof(MAPTYPE),
104                          GFP_ATOMIC);
105         if (bitmap == NULL)
106                 return -ENOMEM;
107
108         iter_node = src->node;
109         do {
110                 bitmap_byte = iter_node->startbit / 8;
111                 bitmask = 0x80;
112                 node_val = iter_node->map;
113                 do {
114                         if (bitmask == 0) {
115                                 bitmap_byte++;
116                                 bitmask = 0x80;
117                         }
118                         if (node_val & (MAPTYPE)0x01)
119                                 bitmap[bitmap_byte] |= bitmask;
120                         node_val >>= 1;
121                         bitmask >>= 1;
122                 } while (node_val > 0);
123                 iter_node = iter_node->next;
124         } while (iter_node);
125
126         *dst = bitmap;
127         *dst_len = bitmap_len;
128         return 0;
129 }
130
131 /**
132  * ebitmap_import - Import an unsigned char bitmap string into an ebitmap
133  * @src: the bitmap string
134  * @src_len: the bitmap length in bytes
135  * @dst: the empty ebitmap
136  *
137  * Description:
138  * This function takes a little endian bitmap string in src and imports it into
139  * the ebitmap pointed to by dst.  Returns zero on success, negative values on
140  * failure.
141  *
142  */
143 int ebitmap_import(const unsigned char *src,
144                    size_t src_len,
145                    struct ebitmap *dst)
146 {
147         size_t src_off = 0;
148         size_t node_limit;
149         struct ebitmap_node *node_new;
150         struct ebitmap_node *node_last = NULL;
151         u32 i_byte;
152         u32 i_bit;
153         unsigned char src_byte;
154
155         while (src_off < src_len) {
156                 if (src_len - src_off >= sizeof(MAPTYPE)) {
157                         if (*(MAPTYPE *)&src[src_off] == 0) {
158                                 src_off += sizeof(MAPTYPE);
159                                 continue;
160                         }
161                         node_limit = sizeof(MAPTYPE);
162                 } else {
163                         for (src_byte = 0, i_byte = src_off;
164                              i_byte < src_len && src_byte == 0;
165                              i_byte++)
166                                 src_byte |= src[i_byte];
167                         if (src_byte == 0)
168                                 break;
169                         node_limit = src_len - src_off;
170                 }
171
172                 node_new = kzalloc(sizeof(*node_new), GFP_ATOMIC);
173                 if (unlikely(node_new == NULL)) {
174                         ebitmap_destroy(dst);
175                         return -ENOMEM;
176                 }
177                 node_new->startbit = src_off * 8;
178                 for (i_byte = 0; i_byte < node_limit; i_byte++) {
179                         src_byte = src[src_off++];
180                         for (i_bit = i_byte * 8; src_byte != 0; i_bit++) {
181                                 if (src_byte & 0x80)
182                                         node_new->map |= MAPBIT << i_bit;
183                                 src_byte <<= 1;
184                         }
185                 }
186
187                 if (node_last != NULL)
188                         node_last->next = node_new;
189                 else
190                         dst->node = node_new;
191                 node_last = node_new;
192         }
193
194         if (likely(node_last != NULL))
195                 dst->highbit = node_last->startbit + MAPSIZE;
196         else
197                 ebitmap_init(dst);
198
199         return 0;
200 }
201
202 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
203 {
204         struct ebitmap_node *n1, *n2;
205
206         if (e1->highbit < e2->highbit)
207                 return 0;
208
209         n1 = e1->node;
210         n2 = e2->node;
211         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
212                 if (n1->startbit < n2->startbit) {
213                         n1 = n1->next;
214                         continue;
215                 }
216                 if ((n1->map & n2->map) != n2->map)
217                         return 0;
218
219                 n1 = n1->next;
220                 n2 = n2->next;
221         }
222
223         if (n2)
224                 return 0;
225
226         return 1;
227 }
228
229 int ebitmap_get_bit(struct ebitmap *e, unsigned long bit)
230 {
231         struct ebitmap_node *n;
232
233         if (e->highbit < bit)
234                 return 0;
235
236         n = e->node;
237         while (n && (n->startbit <= bit)) {
238                 if ((n->startbit + MAPSIZE) > bit) {
239                         if (n->map & (MAPBIT << (bit - n->startbit)))
240                                 return 1;
241                         else
242                                 return 0;
243                 }
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) {
257                 if ((n->startbit + MAPSIZE) > bit) {
258                         if (value) {
259                                 n->map |= (MAPBIT << (bit - n->startbit));
260                         } else {
261                                 n->map &= ~(MAPBIT << (bit - n->startbit));
262                                 if (!n->map) {
263                                         /* drop this node from the bitmap */
264
265                                         if (!n->next) {
266                                                 /*
267                                                  * this was the highest map
268                                                  * within the bitmap
269                                                  */
270                                                 if (prev)
271                                                         e->highbit = prev->startbit + MAPSIZE;
272                                                 else
273                                                         e->highbit = 0;
274                                         }
275                                         if (prev)
276                                                 prev->next = n->next;
277                                         else
278                                                 e->node = n->next;
279
280                                         kfree(n);
281                                 }
282                         }
283                         return 0;
284                 }
285                 prev = n;
286                 n = n->next;
287         }
288
289         if (!value)
290                 return 0;
291
292         new = kzalloc(sizeof(*new), GFP_ATOMIC);
293         if (!new)
294                 return -ENOMEM;
295
296         new->startbit = bit & ~(MAPSIZE - 1);
297         new->map = (MAPBIT << (bit - new->startbit));
298
299         if (!n)
300                 /* this node will be the highest map within the bitmap */
301                 e->highbit = new->startbit + MAPSIZE;
302
303         if (prev) {
304                 new->next = prev->next;
305                 prev->next = new;
306         } else {
307                 new->next = e->node;
308                 e->node = new;
309         }
310
311         return 0;
312 }
313
314 void ebitmap_destroy(struct ebitmap *e)
315 {
316         struct ebitmap_node *n, *temp;
317
318         if (!e)
319                 return;
320
321         n = e->node;
322         while (n) {
323                 temp = n;
324                 n = n->next;
325                 kfree(temp);
326         }
327
328         e->highbit = 0;
329         e->node = NULL;
330         return;
331 }
332
333 int ebitmap_read(struct ebitmap *e, void *fp)
334 {
335         int rc;
336         struct ebitmap_node *n, *l;
337         __le32 buf[3];
338         u32 mapsize, count, i;
339         __le64 map;
340
341         ebitmap_init(e);
342
343         rc = next_entry(buf, fp, sizeof buf);
344         if (rc < 0)
345                 goto out;
346
347         mapsize = le32_to_cpu(buf[0]);
348         e->highbit = le32_to_cpu(buf[1]);
349         count = le32_to_cpu(buf[2]);
350
351         if (mapsize != MAPSIZE) {
352                 printk(KERN_ERR "security: ebitmap: map size %u does not "
353                        "match my size %Zd (high bit was %d)\n", mapsize,
354                        MAPSIZE, e->highbit);
355                 goto bad;
356         }
357         if (!e->highbit) {
358                 e->node = NULL;
359                 goto ok;
360         }
361         if (e->highbit & (MAPSIZE - 1)) {
362                 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
363                        "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
364                 goto bad;
365         }
366         l = NULL;
367         for (i = 0; i < count; i++) {
368                 rc = next_entry(buf, fp, sizeof(u32));
369                 if (rc < 0) {
370                         printk(KERN_ERR "security: ebitmap: truncated map\n");
371                         goto bad;
372                 }
373                 n = kzalloc(sizeof(*n), GFP_KERNEL);
374                 if (!n) {
375                         printk(KERN_ERR "security: ebitmap: out of memory\n");
376                         rc = -ENOMEM;
377                         goto bad;
378                 }
379
380                 n->startbit = le32_to_cpu(buf[0]);
381
382                 if (n->startbit & (MAPSIZE - 1)) {
383                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
384                                "not a multiple of the map size (%Zd)\n",
385                                n->startbit, MAPSIZE);
386                         goto bad_free;
387                 }
388                 if (n->startbit > (e->highbit - MAPSIZE)) {
389                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
390                                "beyond the end of the bitmap (%Zd)\n",
391                                n->startbit, (e->highbit - MAPSIZE));
392                         goto bad_free;
393                 }
394                 rc = next_entry(&map, fp, sizeof(u64));
395                 if (rc < 0) {
396                         printk(KERN_ERR "security: ebitmap: truncated map\n");
397                         goto bad_free;
398                 }
399                 n->map = le64_to_cpu(map);
400
401                 if (!n->map) {
402                         printk(KERN_ERR "security: ebitmap: null map in "
403                                "ebitmap (startbit %d)\n", n->startbit);
404                         goto bad_free;
405                 }
406                 if (l) {
407                         if (n->startbit <= l->startbit) {
408                                 printk(KERN_ERR "security: ebitmap: start "
409                                        "bit %d comes after start bit %d\n",
410                                        n->startbit, l->startbit);
411                                 goto bad_free;
412                         }
413                         l->next = n;
414                 } else
415                         e->node = n;
416
417                 l = n;
418         }
419
420 ok:
421         rc = 0;
422 out:
423         return rc;
424 bad_free:
425         kfree(n);
426 bad:
427         if (!rc)
428                 rc = -EINVAL;
429         ebitmap_destroy(e);
430         goto out;
431 }