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