[NetLabel]: Comment corrections.
[linux-2.6.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.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         struct ebitmap_node *node_new;
149         struct ebitmap_node *node_last = NULL;
150         size_t iter;
151         size_t iter_bit;
152         size_t iter_limit;
153         unsigned char src_byte;
154
155         do {
156                 iter_limit = src_len - src_off;
157                 if (iter_limit >= sizeof(MAPTYPE)) {
158                         if (*(MAPTYPE *)&src[src_off] == 0) {
159                                 src_off += sizeof(MAPTYPE);
160                                 continue;
161                         }
162                         iter_limit = sizeof(MAPTYPE);
163                 } else {
164                         iter = src_off;
165                         src_byte = 0;
166                         do {
167                                 src_byte |= src[iter++];
168                         } while (iter < src_len && src_byte == 0);
169                         if (src_byte == 0)
170                                 break;
171                 }
172
173                 node_new = kzalloc(sizeof(*node_new), GFP_ATOMIC);
174                 if (unlikely(node_new == NULL)) {
175                         ebitmap_destroy(dst);
176                         return -ENOMEM;
177                 }
178                 node_new->startbit = src_off * 8;
179                 iter = 0;
180                 do {
181                         src_byte = src[src_off++];
182                         iter_bit = iter++ * 8;
183                         while (src_byte != 0) {
184                                 if (src_byte & 0x80)
185                                         node_new->map |= MAPBIT << iter_bit;
186                                 iter_bit++;
187                                 src_byte <<= 1;
188                         }
189                 } while (iter < iter_limit);
190
191                 if (node_last != NULL)
192                         node_last->next = node_new;
193                 else
194                         dst->node = node_new;
195                 node_last = node_new;
196         } while (src_off < src_len);
197
198         if (likely(node_last != NULL))
199                 dst->highbit = node_last->startbit + MAPSIZE;
200         else
201                 ebitmap_init(dst);
202
203         return 0;
204 }
205
206 int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2)
207 {
208         struct ebitmap_node *n1, *n2;
209
210         if (e1->highbit < e2->highbit)
211                 return 0;
212
213         n1 = e1->node;
214         n2 = e2->node;
215         while (n1 && n2 && (n1->startbit <= n2->startbit)) {
216                 if (n1->startbit < n2->startbit) {
217                         n1 = n1->next;
218                         continue;
219                 }
220                 if ((n1->map & n2->map) != n2->map)
221                         return 0;
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)) {
242                 if ((n->startbit + MAPSIZE) > bit) {
243                         if (n->map & (MAPBIT << (bit - n->startbit)))
244                                 return 1;
245                         else
246                                 return 0;
247                 }
248                 n = n->next;
249         }
250
251         return 0;
252 }
253
254 int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value)
255 {
256         struct ebitmap_node *n, *prev, *new;
257
258         prev = NULL;
259         n = e->node;
260         while (n && n->startbit <= bit) {
261                 if ((n->startbit + MAPSIZE) > bit) {
262                         if (value) {
263                                 n->map |= (MAPBIT << (bit - n->startbit));
264                         } else {
265                                 n->map &= ~(MAPBIT << (bit - n->startbit));
266                                 if (!n->map) {
267                                         /* drop this node from the bitmap */
268
269                                         if (!n->next) {
270                                                 /*
271                                                  * this was the highest map
272                                                  * within the bitmap
273                                                  */
274                                                 if (prev)
275                                                         e->highbit = prev->startbit + MAPSIZE;
276                                                 else
277                                                         e->highbit = 0;
278                                         }
279                                         if (prev)
280                                                 prev->next = n->next;
281                                         else
282                                                 e->node = n->next;
283
284                                         kfree(n);
285                                 }
286                         }
287                         return 0;
288                 }
289                 prev = n;
290                 n = n->next;
291         }
292
293         if (!value)
294                 return 0;
295
296         new = kzalloc(sizeof(*new), GFP_ATOMIC);
297         if (!new)
298                 return -ENOMEM;
299
300         new->startbit = bit & ~(MAPSIZE - 1);
301         new->map = (MAPBIT << (bit - new->startbit));
302
303         if (!n)
304                 /* this node will be the highest map within the bitmap */
305                 e->highbit = new->startbit + MAPSIZE;
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 {
339         int rc;
340         struct ebitmap_node *n, *l;
341         __le32 buf[3];
342         u32 mapsize, count, i;
343         __le64 map;
344
345         ebitmap_init(e);
346
347         rc = next_entry(buf, fp, sizeof buf);
348         if (rc < 0)
349                 goto out;
350
351         mapsize = le32_to_cpu(buf[0]);
352         e->highbit = le32_to_cpu(buf[1]);
353         count = le32_to_cpu(buf[2]);
354
355         if (mapsize != MAPSIZE) {
356                 printk(KERN_ERR "security: ebitmap: map size %u does not "
357                        "match my size %Zd (high bit was %d)\n", mapsize,
358                        MAPSIZE, e->highbit);
359                 goto bad;
360         }
361         if (!e->highbit) {
362                 e->node = NULL;
363                 goto ok;
364         }
365         if (e->highbit & (MAPSIZE - 1)) {
366                 printk(KERN_ERR "security: ebitmap: high bit (%d) is not a "
367                        "multiple of the map size (%Zd)\n", e->highbit, MAPSIZE);
368                 goto bad;
369         }
370         l = NULL;
371         for (i = 0; i < count; i++) {
372                 rc = next_entry(buf, fp, sizeof(u32));
373                 if (rc < 0) {
374                         printk(KERN_ERR "security: ebitmap: truncated map\n");
375                         goto bad;
376                 }
377                 n = kzalloc(sizeof(*n), GFP_KERNEL);
378                 if (!n) {
379                         printk(KERN_ERR "security: ebitmap: out of memory\n");
380                         rc = -ENOMEM;
381                         goto bad;
382                 }
383
384                 n->startbit = le32_to_cpu(buf[0]);
385
386                 if (n->startbit & (MAPSIZE - 1)) {
387                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
388                                "not a multiple of the map size (%Zd)\n",
389                                n->startbit, MAPSIZE);
390                         goto bad_free;
391                 }
392                 if (n->startbit > (e->highbit - MAPSIZE)) {
393                         printk(KERN_ERR "security: ebitmap start bit (%d) is "
394                                "beyond the end of the bitmap (%Zd)\n",
395                                n->startbit, (e->highbit - MAPSIZE));
396                         goto bad_free;
397                 }
398                 rc = next_entry(&map, fp, sizeof(u64));
399                 if (rc < 0) {
400                         printk(KERN_ERR "security: ebitmap: truncated map\n");
401                         goto bad_free;
402                 }
403                 n->map = le64_to_cpu(map);
404
405                 if (!n->map) {
406                         printk(KERN_ERR "security: ebitmap: null map in "
407                                "ebitmap (startbit %d)\n", n->startbit);
408                         goto bad_free;
409                 }
410                 if (l) {
411                         if (n->startbit <= l->startbit) {
412                                 printk(KERN_ERR "security: ebitmap: start "
413                                        "bit %d comes after start bit %d\n",
414                                        n->startbit, l->startbit);
415                                 goto bad_free;
416                         }
417                         l->next = n;
418                 } else
419                         e->node = n;
420
421                 l = n;
422         }
423
424 ok:
425         rc = 0;
426 out:
427         return rc;
428 bad_free:
429         kfree(n);
430 bad:
431         if (!rc)
432                 rc = -EINVAL;
433         ebitmap_destroy(e);
434         goto out;
435 }