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 < 0) {
 346                         printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 347                         return -1;
 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 -1;
 353
 354                 }
 355                 rc = next_entry(buf32, fp, sizeof(u32)*items2);
 356                 if (rc < 0) {
 357                         printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 358                         return -1;
 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 -1;
 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 -1;
 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 -1;
 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 -1;
 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 -1;
 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 -1;
 407                 }
 408                 return 0;
 409         }
 410
 411         rc = next_entry(buf16, fp, sizeof(u16)*4);
 412         if (rc < 0) {
 413                 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 414                 return -1;
 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 -1;
 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 -1;
 438         }
 439
 440         rc = next_entry(buf32, fp, sizeof(u32));
 441         if (rc < 0) {
 442                 printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 443                 return -1;
 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 -1;
 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                         else
 491                                 rc = -EINVAL;
 492                         goto bad;
 493                 }
 494         }
 495
 496         rc = 0;
 497 out:
 498         return rc;
 499
 500 bad:
 501         avtab_destroy(a);
 502         goto out;
 503 }
 504
 505 void avtab_cache_init(void)
 506 {
 507         avtab_node_cachep = kmem_cache_create("avtab_node",
 508                                               sizeof(struct avtab_node),
 509                                               0, SLAB_PANIC, NULL);
 510 }
 511
 512 void avtab_cache_destroy(void)
 513 {
 514         kmem_cache_destroy(avtab_node_cachep);
 515 }