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
  17 #include <linux/kernel.h>
  18 #include <linux/slab.h>
  19 #include <linux/vmalloc.h>
  20 #include <linux/errno.h>
  21
  22 #include "avtab.h"
  23 #include "policydb.h"
  24
  25 #define AVTAB_HASH(keyp) \
  26 ((keyp->target_class + \
  27  (keyp->target_type << 2) + \
  28  (keyp->source_type << 9)) & \
  29  AVTAB_HASH_MASK)
  30
  31 static kmem_cache_t *avtab_node_cachep;
  32
  33 static struct avtab_node*
  34 avtab_insert_node(struct avtab *h, int hvalue, struct avtab_node * prev, struct avtab_node * cur,
  35                   struct avtab_key *key, struct avtab_datum *datum)
  36 {
  37         struct avtab_node * newnode;
  38         newnode = kmem_cache_alloc(avtab_node_cachep, SLAB_KERNEL);
  39         if (newnode == NULL)
  40                 return NULL;
  41         memset(newnode, 0, sizeof(struct avtab_node));
  42         newnode->key = *key;
  43         newnode->datum = *datum;
  44         if (prev) {
  45                 newnode->next = prev->next;
  46                 prev->next = newnode;
  47         } else {
  48                 newnode->next = h->htable[hvalue];
  49                 h->htable[hvalue] = newnode;
  50         }
  51
  52         h->nel++;
  53         return newnode;
  54 }
  55
  56 int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
  57 {
  58         int hvalue;
  59         struct avtab_node *prev, *cur, *newnode;
  60
  61         if (!h)
  62                 return -EINVAL;
  63
  64         hvalue = AVTAB_HASH(key);
  65         for (prev = NULL, cur = h->htable[hvalue];
  66              cur;
  67              prev = cur, cur = cur->next) {
  68                 if (key->source_type == cur->key.source_type &&
  69                     key->target_type == cur->key.target_type &&
  70                     key->target_class == cur->key.target_class &&
  71                     (datum->specified & cur->datum.specified))
  72                         return -EEXIST;
  73                 if (key->source_type < cur->key.source_type)
  74                         break;
  75                 if (key->source_type == cur->key.source_type &&
  76                     key->target_type < cur->key.target_type)
  77                         break;
  78                 if (key->source_type == cur->key.source_type &&
  79                     key->target_type == cur->key.target_type &&
  80                     key->target_class < cur->key.target_class)
  81                         break;
  82         }
  83
  84         newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
  85         if(!newnode)
  86                 return -ENOMEM;
  87
  88         return 0;
  89 }
  90
  91 /* Unlike avtab_insert(), this function allow multiple insertions of the same
  92  * key/specified mask into the table, as needed by the conditional avtab.
  93  * It also returns a pointer to the node inserted.
  94  */
  95 struct avtab_node *
  96 avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_datum * datum)
  97 {
  98         int hvalue;
  99         struct avtab_node *prev, *cur, *newnode;
 100
 101         if (!h)
 102                 return NULL;
 103         hvalue = AVTAB_HASH(key);
 104         for (prev = NULL, cur = h->htable[hvalue];
 105              cur;
 106              prev = cur, cur = cur->next) {
 107                 if (key->source_type == cur->key.source_type &&
 108                     key->target_type == cur->key.target_type &&
 109                     key->target_class == cur->key.target_class &&
 110                     (datum->specified & cur->datum.specified))
 111                         break;
 112                 if (key->source_type < cur->key.source_type)
 113                         break;
 114                 if (key->source_type == cur->key.source_type &&
 115                     key->target_type < cur->key.target_type)
 116                         break;
 117                 if (key->source_type == cur->key.source_type &&
 118                     key->target_type == cur->key.target_type &&
 119                     key->target_class < cur->key.target_class)
 120                         break;
 121         }
 122         newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
 123
 124         return newnode;
 125 }
 126
 127 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key, int specified)
 128 {
 129         int hvalue;
 130         struct avtab_node *cur;
 131
 132         if (!h)
 133                 return NULL;
 134
 135         hvalue = AVTAB_HASH(key);
 136         for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 137                 if (key->source_type == cur->key.source_type &&
 138                     key->target_type == cur->key.target_type &&
 139                     key->target_class == cur->key.target_class &&
 140                     (specified & cur->datum.specified))
 141                         return &cur->datum;
 142
 143                 if (key->source_type < cur->key.source_type)
 144                         break;
 145                 if (key->source_type == cur->key.source_type &&
 146                     key->target_type < cur->key.target_type)
 147                         break;
 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                         break;
 152         }
 153
 154         return NULL;
 155 }
 156
 157 /* This search function returns a node pointer, and can be used in
 158  * conjunction with avtab_search_next_node()
 159  */
 160 struct avtab_node*
 161 avtab_search_node(struct avtab *h, struct avtab_key *key, int specified)
 162 {
 163         int hvalue;
 164         struct avtab_node *cur;
 165
 166         if (!h)
 167                 return NULL;
 168
 169         hvalue = AVTAB_HASH(key);
 170         for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 171                 if (key->source_type == cur->key.source_type &&
 172                     key->target_type == cur->key.target_type &&
 173                     key->target_class == cur->key.target_class &&
 174                     (specified & cur->datum.specified))
 175                         return cur;
 176
 177                 if (key->source_type < cur->key.source_type)
 178                         break;
 179                 if (key->source_type == cur->key.source_type &&
 180                     key->target_type < cur->key.target_type)
 181                         break;
 182                 if (key->source_type == cur->key.source_type &&
 183                     key->target_type == cur->key.target_type &&
 184                     key->target_class < cur->key.target_class)
 185                         break;
 186         }
 187         return NULL;
 188 }
 189
 190 struct avtab_node*
 191 avtab_search_node_next(struct avtab_node *node, int specified)
 192 {
 193         struct avtab_node *cur;
 194
 195         if (!node)
 196                 return NULL;
 197
 198         for (cur = node->next; cur; cur = cur->next) {
 199                 if (node->key.source_type == cur->key.source_type &&
 200                     node->key.target_type == cur->key.target_type &&
 201                     node->key.target_class == cur->key.target_class &&
 202                     (specified & cur->datum.specified))
 203                         return cur;
 204
 205                 if (node->key.source_type < cur->key.source_type)
 206                         break;
 207                 if (node->key.source_type == cur->key.source_type &&
 208                     node->key.target_type < cur->key.target_type)
 209                         break;
 210                 if (node->key.source_type == cur->key.source_type &&
 211                     node->key.target_type == cur->key.target_type &&
 212                     node->key.target_class < cur->key.target_class)
 213                         break;
 214         }
 215         return NULL;
 216 }
 217
 218 void avtab_destroy(struct avtab *h)
 219 {
 220         int i;
 221         struct avtab_node *cur, *temp;
 222
 223         if (!h || !h->htable)
 224                 return;
 225
 226         for (i = 0; i < AVTAB_SIZE; i++) {
 227                 cur = h->htable[i];
 228                 while (cur != NULL) {
 229                         temp = cur;
 230                         cur = cur->next;
 231                         kmem_cache_free(avtab_node_cachep, temp);
 232                 }
 233                 h->htable[i] = NULL;
 234         }
 235         vfree(h->htable);
 236         h->htable = NULL;
 237 }
 238
 239
 240 int avtab_map(struct avtab *h,
 241               int (*apply) (struct avtab_key *k,
 242                             struct avtab_datum *d,
 243                             void *args),
 244               void *args)
 245 {
 246         int i, ret;
 247         struct avtab_node *cur;
 248
 249         if (!h)
 250                 return 0;
 251
 252         for (i = 0; i < AVTAB_SIZE; i++) {
 253                 cur = h->htable[i];
 254                 while (cur != NULL) {
 255                         ret = apply(&cur->key, &cur->datum, args);
 256                         if (ret)
 257                                 return ret;
 258                         cur = cur->next;
 259                 }
 260         }
 261         return 0;
 262 }
 263
 264 int avtab_init(struct avtab *h)
 265 {
 266         int i;
 267
 268         h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
 269         if (!h->htable)
 270                 return -ENOMEM;
 271         for (i = 0; i < AVTAB_SIZE; i++)
 272                 h->htable[i] = NULL;
 273         h->nel = 0;
 274         return 0;
 275 }
 276
 277 void avtab_hash_eval(struct avtab *h, char *tag)
 278 {
 279         int i, chain_len, slots_used, max_chain_len;
 280         struct avtab_node *cur;
 281
 282         slots_used = 0;
 283         max_chain_len = 0;
 284         for (i = 0; i < AVTAB_SIZE; i++) {
 285                 cur = h->htable[i];
 286                 if (cur) {
 287                         slots_used++;
 288                         chain_len = 0;
 289                         while (cur) {
 290                                 chain_len++;
 291                                 cur = cur->next;
 292                         }
 293
 294                         if (chain_len > max_chain_len)
 295                                 max_chain_len = chain_len;
 296                 }
 297         }
 298
 299         printk(KERN_INFO "%s:  %d entries and %d/%d buckets used, longest "
 300                "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
 301                max_chain_len);
 302 }
 303
 304 int avtab_read_item(void *fp, struct avtab_datum *avdatum, struct avtab_key *avkey)
 305 {
 306         __u32 *buf;
 307         __u32 items, items2;
 308
 309         memset(avkey, 0, sizeof(struct avtab_key));
 310         memset(avdatum, 0, sizeof(struct avtab_datum));
 311
 312         buf = next_entry(fp, sizeof(__u32));
 313         if (!buf) {
 314                 printk(KERN_ERR "security: avtab: truncated entry\n");
 315                 goto bad;
 316         }
 317         items2 = le32_to_cpu(buf[0]);
 318         buf = next_entry(fp, sizeof(__u32)*items2);
 319         if (!buf) {
 320                 printk(KERN_ERR "security: avtab: truncated entry\n");
 321                 goto bad;
 322         }
 323         items = 0;
 324         avkey->source_type = le32_to_cpu(buf[items++]);
 325         avkey->target_type = le32_to_cpu(buf[items++]);
 326         avkey->target_class = le32_to_cpu(buf[items++]);
 327         avdatum->specified = le32_to_cpu(buf[items++]);
 328         if (!(avdatum->specified & (AVTAB_AV | AVTAB_TYPE))) {
 329                 printk(KERN_ERR "security: avtab: null entry\n");
 330                 goto bad;
 331         }
 332         if ((avdatum->specified & AVTAB_AV) &&
 333             (avdatum->specified & AVTAB_TYPE)) {
 334                 printk(KERN_ERR "security: avtab: entry has both access vectors and types\n");
 335                 goto bad;
 336         }
 337         if (avdatum->specified & AVTAB_AV) {
 338                 if (avdatum->specified & AVTAB_ALLOWED)
 339                         avtab_allowed(avdatum) = le32_to_cpu(buf[items++]);
 340                 if (avdatum->specified & AVTAB_AUDITDENY)
 341                         avtab_auditdeny(avdatum) = le32_to_cpu(buf[items++]);
 342                 if (avdatum->specified & AVTAB_AUDITALLOW)
 343                         avtab_auditallow(avdatum) = le32_to_cpu(buf[items++]);
 344         } else {
 345                 if (avdatum->specified & AVTAB_TRANSITION)
 346                         avtab_transition(avdatum) = le32_to_cpu(buf[items++]);
 347                 if (avdatum->specified & AVTAB_CHANGE)
 348                         avtab_change(avdatum) = le32_to_cpu(buf[items++]);
 349                 if (avdatum->specified & AVTAB_MEMBER)
 350                         avtab_member(avdatum) = le32_to_cpu(buf[items++]);
 351         }
 352         if (items != items2) {
 353                 printk(KERN_ERR "security: avtab: entry only had %d items, expected %d\n",
 354                        items2, items);
 355                 goto bad;
 356         }
 357
 358         return 0;
 359 bad:
 360         return -1;
 361 }
 362
 363 int avtab_read(struct avtab *a, void *fp, u32 config)
 364 {
 365         int i, rc = -EINVAL;
 366         struct avtab_key avkey;
 367         struct avtab_datum avdatum;
 368         u32 *buf;
 369         u32 nel;
 370
 371
 372         buf = next_entry(fp, sizeof(u32));
 373         if (!buf) {
 374                 printk(KERN_ERR "security: avtab: truncated table\n");
 375                 goto bad;
 376         }
 377         nel = le32_to_cpu(buf[0]);
 378         if (!nel) {
 379                 printk(KERN_ERR "security: avtab: table is empty\n");
 380                 goto bad;
 381         }
 382         for (i = 0; i < nel; i++) {
 383                 if (avtab_read_item(fp, &avdatum, &avkey))
 384                         goto bad;
 385                 rc = avtab_insert(a, &avkey, &avdatum);
 386                 if (rc) {
 387                         if (rc == -ENOMEM)
 388                                 printk(KERN_ERR "security: avtab: out of memory\n");
 389                         if (rc == -EEXIST)
 390                                 printk(KERN_ERR "security: avtab: duplicate entry\n");
 391                         goto bad;
 392                 }
 393         }
 394
 395         rc = 0;
 396 out:
 397         return rc;
 398
 399 bad:
 400         avtab_destroy(a);
 401         goto out;
 402 }
 403
 404 void avtab_cache_init(void)
 405 {
 406         avtab_node_cachep = kmem_cache_create("avtab_node",
 407                                               sizeof(struct avtab_node),
 408                                               0, SLAB_PANIC, NULL, NULL);
 409 }