929480c6c4306e874eff82db107045b944cdd33b
[linux-2.6.git] / security / selinux / ss / avtab.c
1 /*
2  * Implementation of the access vector table type.
3  *
4  * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
5  */
6
7 /* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com>
8  *
9  *      Added conditional policy language extensions
10  *
11  * Copyright (C) 2003 Tresys Technology, LLC
12  *      This program is free software; you can redistribute it and/or modify
13  *      it under the terms of the GNU General Public License as published by
14  *      the Free Software Foundation, version 2.
15  *
16  * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
17  *      Tuned number of hash slots for avtab to reduce memory usage
18  */
19
20 #include <linux/kernel.h>
21 #include <linux/slab.h>
22 #include <linux/errno.h>
23 #include "avtab.h"
24 #include "policydb.h"
25
26 static struct kmem_cache *avtab_node_cachep;
27
28 static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
29 {
30         return ((keyp->target_class + (keyp->target_type << 2) +
31                  (keyp->source_type << 9)) & mask);
32 }
33
34 static struct avtab_node*
35 avtab_insert_node(struct avtab *h, int hvalue,
36                   struct avtab_node *prev, struct avtab_node *cur,
37                   struct avtab_key *key, struct avtab_datum *datum)
38 {
39         struct avtab_node *newnode;
40         newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
41         if (newnode == NULL)
42                 return NULL;
43         newnode->key = *key;
44         newnode->datum = *datum;
45         if (prev) {
46                 newnode->next = prev->next;
47                 prev->next = newnode;
48         } else {
49                 newnode->next = h->htable[hvalue];
50                 h->htable[hvalue] = newnode;
51         }
52
53         h->nel++;
54         return newnode;
55 }
56
57 static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
58 {
59         int hvalue;
60         struct avtab_node *prev, *cur, *newnode;
61         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
62
63         if (!h || !h->htable)
64                 return -EINVAL;
65
66         hvalue = avtab_hash(key, h->mask);
67         for (prev = NULL, cur = h->htable[hvalue];
68              cur;
69              prev = cur, cur = cur->next) {
70                 if (key->source_type == cur->key.source_type &&
71                     key->target_type == cur->key.target_type &&
72                     key->target_class == cur->key.target_class &&
73                     (specified & cur->key.specified))
74                         return -EEXIST;
75                 if (key->source_type < cur->key.source_type)
76                         break;
77                 if (key->source_type == cur->key.source_type &&
78                     key->target_type < cur->key.target_type)
79                         break;
80                 if (key->source_type == cur->key.source_type &&
81                     key->target_type == cur->key.target_type &&
82                     key->target_class < cur->key.target_class)
83                         break;
84         }
85
86         newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
87         if (!newnode)
88                 return -ENOMEM;
89
90         return 0;
91 }
92
93 /* Unlike avtab_insert(), this function allow multiple insertions of the same
94  * key/specified mask into the table, as needed by the conditional avtab.
95  * It also returns a pointer to the node inserted.
96  */
97 struct avtab_node *
98 avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
99 {
100         int hvalue;
101         struct avtab_node *prev, *cur;
102         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
103
104         if (!h || !h->htable)
105                 return NULL;
106         hvalue = avtab_hash(key, h->mask);
107         for (prev = NULL, cur = h->htable[hvalue];
108              cur;
109              prev = cur, cur = cur->next) {
110                 if (key->source_type == cur->key.source_type &&
111                     key->target_type == cur->key.target_type &&
112                     key->target_class == cur->key.target_class &&
113                     (specified & cur->key.specified))
114                         break;
115                 if (key->source_type < cur->key.source_type)
116                         break;
117                 if (key->source_type == cur->key.source_type &&
118                     key->target_type < cur->key.target_type)
119                         break;
120                 if (key->source_type == cur->key.source_type &&
121                     key->target_type == cur->key.target_type &&
122                     key->target_class < cur->key.target_class)
123                         break;
124         }
125         return avtab_insert_node(h, hvalue, prev, cur, key, datum);
126 }
127
128 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
129 {
130         int hvalue;
131         struct avtab_node *cur;
132         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
133
134         if (!h || !h->htable)
135                 return NULL;
136
137         hvalue = avtab_hash(key, h->mask);
138         for (cur = h->htable[hvalue]; cur; cur = cur->next) {
139                 if (key->source_type == cur->key.source_type &&
140                     key->target_type == cur->key.target_type &&
141                     key->target_class == cur->key.target_class &&
142                     (specified & cur->key.specified))
143                         return &cur->datum;
144
145                 if (key->source_type < cur->key.source_type)
146                         break;
147                 if (key->source_type == cur->key.source_type &&
148                     key->target_type < cur->key.target_type)
149                         break;
150                 if (key->source_type == cur->key.source_type &&
151                     key->target_type == cur->key.target_type &&
152                     key->target_class < cur->key.target_class)
153                         break;
154         }
155
156         return NULL;
157 }
158
159 /* This search function returns a node pointer, and can be used in
160  * conjunction with avtab_search_next_node()
161  */
162 struct avtab_node*
163 avtab_search_node(struct avtab *h, struct avtab_key *key)
164 {
165         int hvalue;
166         struct avtab_node *cur;
167         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
168
169         if (!h || !h->htable)
170                 return NULL;
171
172         hvalue = avtab_hash(key, h->mask);
173         for (cur = h->htable[hvalue]; cur; cur = cur->next) {
174                 if (key->source_type == cur->key.source_type &&
175                     key->target_type == cur->key.target_type &&
176                     key->target_class == cur->key.target_class &&
177                     (specified & cur->key.specified))
178                         return cur;
179
180                 if (key->source_type < cur->key.source_type)
181                         break;
182                 if (key->source_type == cur->key.source_type &&
183                     key->target_type < cur->key.target_type)
184                         break;
185                 if (key->source_type == cur->key.source_type &&
186                     key->target_type == cur->key.target_type &&
187                     key->target_class < cur->key.target_class)
188                         break;
189         }
190         return NULL;
191 }
192
193 struct avtab_node*
194 avtab_search_node_next(struct avtab_node *node, int specified)
195 {
196         struct avtab_node *cur;
197
198         if (!node)
199                 return NULL;
200
201         specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
202         for (cur = node->next; cur; cur = cur->next) {
203                 if (node->key.source_type == cur->key.source_type &&
204                     node->key.target_type == cur->key.target_type &&
205                     node->key.target_class == cur->key.target_class &&
206                     (specified & cur->key.specified))
207                         return cur;
208
209                 if (node->key.source_type < cur->key.source_type)
210                         break;
211                 if (node->key.source_type == cur->key.source_type &&
212                     node->key.target_type < cur->key.target_type)
213                         break;
214                 if (node->key.source_type == cur->key.source_type &&
215                     node->key.target_type == cur->key.target_type &&
216                     node->key.target_class < cur->key.target_class)
217                         break;
218         }
219         return NULL;
220 }
221
222 void avtab_destroy(struct avtab *h)
223 {
224         int i;
225         struct avtab_node *cur, *temp;
226
227         if (!h || !h->htable)
228                 return;
229
230         for (i = 0; i < h->nslot; i++) {
231                 cur = h->htable[i];
232                 while (cur) {
233                         temp = cur;
234                         cur = cur->next;
235                         kmem_cache_free(avtab_node_cachep, temp);
236                 }
237                 h->htable[i] = NULL;
238         }
239         kfree(h->htable);
240         h->htable = NULL;
241         h->nslot = 0;
242         h->mask = 0;
243 }
244
245 int avtab_init(struct avtab *h)
246 {
247         h->htable = NULL;
248         h->nel = 0;
249         return 0;
250 }
251
252 int avtab_alloc(struct avtab *h, u32 nrules)
253 {
254         u16 mask = 0;
255         u32 shift = 0;
256         u32 work = nrules;
257         u32 nslot = 0;
258
259         if (nrules == 0)
260                 goto avtab_alloc_out;
261
262         while (work) {
263                 work  = work >> 1;
264                 shift++;
265         }
266         if (shift > 2)
267                 shift = shift - 2;
268         nslot = 1 << shift;
269         if (nslot > MAX_AVTAB_SIZE)
270                 nslot = MAX_AVTAB_SIZE;
271         mask = nslot - 1;
272
273         h->htable = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL);
274         if (!h->htable)
275                 return -ENOMEM;
276
277  avtab_alloc_out:
278         h->nel = 0;
279         h->nslot = nslot;
280         h->mask = mask;
281         printk(KERN_DEBUG "SELinux: %d avtab hash slots, %d rules.\n",
282                h->nslot, nrules);
283         return 0;
284 }
285
286 void avtab_hash_eval(struct avtab *h, char *tag)
287 {
288         int i, chain_len, slots_used, max_chain_len;
289         unsigned long long chain2_len_sum;
290         struct avtab_node *cur;
291
292         slots_used = 0;
293         max_chain_len = 0;
294         chain2_len_sum = 0;
295         for (i = 0; i < h->nslot; i++) {
296                 cur = h->htable[i];
297                 if (cur) {
298                         slots_used++;
299                         chain_len = 0;
300                         while (cur) {
301                                 chain_len++;
302                                 cur = cur->next;
303                         }
304
305                         if (chain_len > max_chain_len)
306                                 max_chain_len = chain_len;
307                         chain2_len_sum += chain_len * chain_len;
308                 }
309         }
310
311         printk(KERN_DEBUG "SELinux: %s:  %d entries and %d/%d buckets used, "
312                "longest chain length %d sum of chain length^2 %llu\n",
313                tag, h->nel, slots_used, h->nslot, max_chain_len,
314                chain2_len_sum);
315 }
316
317 static uint16_t spec_order[] = {
318         AVTAB_ALLOWED,
319         AVTAB_AUDITDENY,
320         AVTAB_AUDITALLOW,
321         AVTAB_TRANSITION,
322         AVTAB_CHANGE,
323         AVTAB_MEMBER
324 };
325
326 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
327                     int (*insertf)(struct avtab *a, struct avtab_key *k,
328                                    struct avtab_datum *d, void *p),
329                     void *p)
330 {
331         __le16 buf16[4];
332         u16 enabled;
333         __le32 buf32[7];
334         u32 items, items2, val, vers = pol->policyvers;
335         struct avtab_key key;
336         struct avtab_datum datum;
337         int i, rc;
338         unsigned set;
339
340         memset(&key, 0, sizeof(struct avtab_key));
341         memset(&datum, 0, sizeof(struct avtab_datum));
342
343         if (vers < POLICYDB_VERSION_AVTAB) {
344                 rc = next_entry(buf32, fp, sizeof(u32));
345                 if (rc) {
346                         printk(KERN_ERR "SELinux: avtab: truncated entry\n");
347                         return rc;
348                 }
349                 items2 = le32_to_cpu(buf32[0]);
350                 if (items2 > ARRAY_SIZE(buf32)) {
351                         printk(KERN_ERR "SELinux: avtab: entry overflow\n");
352                         return -EINVAL;
353
354                 }
355                 rc = next_entry(buf32, fp, sizeof(u32)*items2);
356                 if (rc) {
357                         printk(KERN_ERR "SELinux: avtab: truncated entry\n");
358                         return rc;
359                 }
360                 items = 0;
361
362                 val = le32_to_cpu(buf32[items++]);
363                 key.source_type = (u16)val;
364                 if (key.source_type != val) {
365                         printk(KERN_ERR "SELinux: avtab: truncated source type\n");
366                         return -EINVAL;
367                 }
368                 val = le32_to_cpu(buf32[items++]);
369                 key.target_type = (u16)val;
370                 if (key.target_type != val) {
371                         printk(KERN_ERR "SELinux: avtab: truncated target type\n");
372                         return -EINVAL;
373                 }
374                 val = le32_to_cpu(buf32[items++]);
375                 key.target_class = (u16)val;
376                 if (key.target_class != val) {
377                         printk(KERN_ERR "SELinux: avtab: truncated target class\n");
378                         return -EINVAL;
379                 }
380
381                 val = le32_to_cpu(buf32[items++]);
382                 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
383
384                 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
385                         printk(KERN_ERR "SELinux: avtab: null entry\n");
386                         return -EINVAL;
387                 }
388                 if ((val & AVTAB_AV) &&
389                     (val & AVTAB_TYPE)) {
390                         printk(KERN_ERR "SELinux: avtab: entry has both access vectors and types\n");
391                         return -EINVAL;
392                 }
393
394                 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
395                         if (val & spec_order[i]) {
396                                 key.specified = spec_order[i] | enabled;
397                                 datum.data = le32_to_cpu(buf32[items++]);
398                                 rc = insertf(a, &key, &datum, p);
399                                 if (rc)
400                                         return rc;
401                         }
402                 }
403
404                 if (items != items2) {
405                         printk(KERN_ERR "SELinux: avtab: entry only had %d items, expected %d\n", items2, items);
406                         return -EINVAL;
407                 }
408                 return 0;
409         }
410
411         rc = next_entry(buf16, fp, sizeof(u16)*4);
412         if (rc) {
413                 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
414                 return rc;
415         }
416
417         items = 0;
418         key.source_type = le16_to_cpu(buf16[items++]);
419         key.target_type = le16_to_cpu(buf16[items++]);
420         key.target_class = le16_to_cpu(buf16[items++]);
421         key.specified = le16_to_cpu(buf16[items++]);
422
423         if (!policydb_type_isvalid(pol, key.source_type) ||
424             !policydb_type_isvalid(pol, key.target_type) ||
425             !policydb_class_isvalid(pol, key.target_class)) {
426                 printk(KERN_ERR "SELinux: avtab: invalid type or class\n");
427                 return -EINVAL;
428         }
429
430         set = 0;
431         for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
432                 if (key.specified & spec_order[i])
433                         set++;
434         }
435         if (!set || set > 1) {
436                 printk(KERN_ERR "SELinux:  avtab:  more than one specifier\n");
437                 return -EINVAL;
438         }
439
440         rc = next_entry(buf32, fp, sizeof(u32));
441         if (rc) {
442                 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
443                 return rc;
444         }
445         datum.data = le32_to_cpu(*buf32);
446         if ((key.specified & AVTAB_TYPE) &&
447             !policydb_type_isvalid(pol, datum.data)) {
448                 printk(KERN_ERR "SELinux: avtab: invalid type\n");
449                 return -EINVAL;
450         }
451         return insertf(a, &key, &datum, p);
452 }
453
454 static int avtab_insertf(struct avtab *a, struct avtab_key *k,
455                          struct avtab_datum *d, void *p)
456 {
457         return avtab_insert(a, k, d);
458 }
459
460 int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
461 {
462         int rc;
463         __le32 buf[1];
464         u32 nel, i;
465
466
467         rc = next_entry(buf, fp, sizeof(u32));
468         if (rc < 0) {
469                 printk(KERN_ERR "SELinux: avtab: truncated table\n");
470                 goto bad;
471         }
472         nel = le32_to_cpu(buf[0]);
473         if (!nel) {
474                 printk(KERN_ERR "SELinux: avtab: table is empty\n");
475                 rc = -EINVAL;
476                 goto bad;
477         }
478
479         rc = avtab_alloc(a, nel);
480         if (rc)
481                 goto bad;
482
483         for (i = 0; i < nel; i++) {
484                 rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
485                 if (rc) {
486                         if (rc == -ENOMEM)
487                                 printk(KERN_ERR "SELinux: avtab: out of memory\n");
488                         else if (rc == -EEXIST)
489                                 printk(KERN_ERR "SELinux: avtab: duplicate entry\n");
490
491                         goto bad;
492                 }
493         }
494
495         rc = 0;
496 out:
497         return rc;
498
499 bad:
500         avtab_destroy(a);
501         goto out;
502 }
503
504 void avtab_cache_init(void)
505 {
506         avtab_node_cachep = kmem_cache_create("avtab_node",
507                                               sizeof(struct avtab_node),
508                                               0, SLAB_PANIC, NULL);
509 }
510
511 void avtab_cache_destroy(void)
512 {
513         kmem_cache_destroy(avtab_node_cachep);
514 }