security/selinux/ss/avtab.c

   1 /*
   2  * Implementation of the access vector table type.
   3  *
   4  * Author : Stephen Smalley, <[email protected]>
   5  */
   6
   7 /* Updated: Frank Mayer <[email protected]> and Karl MacMillan <[email protected]>
   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 <[email protected]>
  17  *      Tuned number of hash slots for avtab to reduce memory usage
  18  */
  19
  20 #include <linux/bitops.h>
  21 #include <linux/kernel.h>
  22 #include <linux/slab.h>
  23 #include <linux/errno.h>
  24 #include "avtab.h"
  25 #include "policydb.h"
  26
  27 static struct kmem_cache *avtab_node_cachep __ro_after_init;
  28 static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
  29
  30 /* Based on MurmurHash3, written by Austin Appleby and placed in the
  31  * public domain.
  32  */
  33 static inline u32 avtab_hash(const struct avtab_key *keyp, u32 mask)
  34 {
  35         static const u32 c1 = 0xcc9e2d51;
  36         static const u32 c2 = 0x1b873593;
  37         static const u32 r1 = 15;
  38         static const u32 r2 = 13;
  39         static const u32 m  = 5;
  40         static const u32 n  = 0xe6546b64;
  41
  42         u32 hash = 0;
  43
  44 #define mix(input) do { \
  45                 u32 v = input; \
  46                 v *= c1; \
  47                 v = (v << r1) | (v >> (32 - r1)); \
  48                 v *= c2; \
  49                 hash ^= v; \
  50                 hash = (hash << r2) | (hash >> (32 - r2)); \
  51                 hash = hash * m + n; \
  52         } while (0)
  53
  54         mix(keyp->target_class);
  55         mix(keyp->target_type);
  56         mix(keyp->source_type);
  57
  58 #undef mix
  59
  60         hash ^= hash >> 16;
  61         hash *= 0x85ebca6b;
  62         hash ^= hash >> 13;
  63         hash *= 0xc2b2ae35;
  64         hash ^= hash >> 16;
  65
  66         return hash & mask;
  67 }
  68
  69 static struct avtab_node*
  70 avtab_insert_node(struct avtab *h, struct avtab_node **dst,
  71                   const struct avtab_key *key, const struct avtab_datum *datum)
  72 {
  73         struct avtab_node *newnode;
  74         struct avtab_extended_perms *xperms;
  75         newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
  76         if (newnode == NULL)
  77                 return NULL;
  78         newnode->key = *key;
  79
  80         if (key->specified & AVTAB_XPERMS) {
  81                 xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL);
  82                 if (xperms == NULL) {
  83                         kmem_cache_free(avtab_node_cachep, newnode);
  84                         return NULL;
  85                 }
  86                 *xperms = *(datum->u.xperms);
  87                 newnode->datum.u.xperms = xperms;
  88         } else {
  89                 newnode->datum.u.data = datum->u.data;
  90         }
  91
  92         newnode->next = *dst;
  93         *dst = newnode;
  94
  95         h->nel++;
  96         return newnode;
  97 }
  98
  99 static int avtab_insert(struct avtab *h, const struct avtab_key *key,
 100                         const struct avtab_datum *datum)
 101 {
 102         u32 hvalue;
 103         struct avtab_node *prev, *cur, *newnode;
 104         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 105
 106         if (!h || !h->nslot || h->nel == U32_MAX)
 107                 return -EINVAL;
 108
 109         hvalue = avtab_hash(key, h->mask);
 110         for (prev = NULL, cur = h->htable[hvalue];
 111              cur;
 112              prev = cur, cur = cur->next) {
 113                 if (key->source_type == cur->key.source_type &&
 114                     key->target_type == cur->key.target_type &&
 115                     key->target_class == cur->key.target_class &&
 116                     (specified & cur->key.specified)) {
 117                         /* extended perms may not be unique */
 118                         if (specified & AVTAB_XPERMS)
 119                                 break;
 120                         return -EEXIST;
 121                 }
 122                 if (key->source_type < cur->key.source_type)
 123                         break;
 124                 if (key->source_type == cur->key.source_type &&
 125                     key->target_type < cur->key.target_type)
 126                         break;
 127                 if (key->source_type == cur->key.source_type &&
 128                     key->target_type == cur->key.target_type &&
 129                     key->target_class < cur->key.target_class)
 130                         break;
 131         }
 132
 133         newnode = avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue],
 134                                     key, datum);
 135         if (!newnode)
 136                 return -ENOMEM;
 137
 138         return 0;
 139 }
 140
 141 /* Unlike avtab_insert(), this function allow multiple insertions of the same
 142  * key/specified mask into the table, as needed by the conditional avtab.
 143  * It also returns a pointer to the node inserted.
 144  */
 145 struct avtab_node *avtab_insert_nonunique(struct avtab *h,
 146                                           const struct avtab_key *key,
 147                                           const struct avtab_datum *datum)
 148 {
 149         u32 hvalue;
 150         struct avtab_node *prev, *cur;
 151         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 152
 153         if (!h || !h->nslot || h->nel == U32_MAX)
 154                 return NULL;
 155         hvalue = avtab_hash(key, h->mask);
 156         for (prev = NULL, cur = h->htable[hvalue];
 157              cur;
 158              prev = cur, cur = cur->next) {
 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                     (specified & cur->key.specified))
 163                         break;
 164                 if (key->source_type < cur->key.source_type)
 165                         break;
 166                 if (key->source_type == cur->key.source_type &&
 167                     key->target_type < cur->key.target_type)
 168                         break;
 169                 if (key->source_type == cur->key.source_type &&
 170                     key->target_type == cur->key.target_type &&
 171                     key->target_class < cur->key.target_class)
 172                         break;
 173         }
 174         return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue],
 175                                  key, datum);
 176 }
 177
 178 /* This search function returns a node pointer, and can be used in
 179  * conjunction with avtab_search_next_node()
 180  */
 181 struct avtab_node *avtab_search_node(struct avtab *h,
 182                                      const struct avtab_key *key)
 183 {
 184         u32 hvalue;
 185         struct avtab_node *cur;
 186         u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 187
 188         if (!h || !h->nslot)
 189                 return NULL;
 190
 191         hvalue = avtab_hash(key, h->mask);
 192         for (cur = h->htable[hvalue]; cur;
 193              cur = cur->next) {
 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                     (specified & cur->key.specified))
 198                         return cur;
 199
 200                 if (key->source_type < cur->key.source_type)
 201                         break;
 202                 if (key->source_type == cur->key.source_type &&
 203                     key->target_type < cur->key.target_type)
 204                         break;
 205                 if (key->source_type == cur->key.source_type &&
 206                     key->target_type == cur->key.target_type &&
 207                     key->target_class < cur->key.target_class)
 208                         break;
 209         }
 210         return NULL;
 211 }
 212
 213 struct avtab_node*
 214 avtab_search_node_next(struct avtab_node *node, u16 specified)
 215 {
 216         struct avtab_node *cur;
 217
 218         if (!node)
 219                 return NULL;
 220
 221         specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 222         for (cur = node->next; cur; cur = cur->next) {
 223                 if (node->key.source_type == cur->key.source_type &&
 224                     node->key.target_type == cur->key.target_type &&
 225                     node->key.target_class == cur->key.target_class &&
 226                     (specified & cur->key.specified))
 227                         return cur;
 228
 229                 if (node->key.source_type < cur->key.source_type)
 230                         break;
 231                 if (node->key.source_type == cur->key.source_type &&
 232                     node->key.target_type < cur->key.target_type)
 233                         break;
 234                 if (node->key.source_type == cur->key.source_type &&
 235                     node->key.target_type == cur->key.target_type &&
 236                     node->key.target_class < cur->key.target_class)
 237                         break;
 238         }
 239         return NULL;
 240 }
 241
 242 void avtab_destroy(struct avtab *h)
 243 {
 244         u32 i;
 245         struct avtab_node *cur, *temp;
 246
 247         if (!h)
 248                 return;
 249
 250         for (i = 0; i < h->nslot; i++) {
 251                 cur = h->htable[i];
 252                 while (cur) {
 253                         temp = cur;
 254                         cur = cur->next;
 255                         if (temp->key.specified & AVTAB_XPERMS)
 256                                 kmem_cache_free(avtab_xperms_cachep,
 257                                                 temp->datum.u.xperms);
 258                         kmem_cache_free(avtab_node_cachep, temp);
 259                 }
 260         }
 261         kvfree(h->htable);
 262         h->htable = NULL;
 263         h->nel = 0;
 264         h->nslot = 0;
 265         h->mask = 0;
 266 }
 267
 268 void avtab_init(struct avtab *h)
 269 {
 270         h->htable = NULL;
 271         h->nel = 0;
 272         h->nslot = 0;
 273         h->mask = 0;
 274 }
 275
 276 static int avtab_alloc_common(struct avtab *h, u32 nslot)
 277 {
 278         if (!nslot)
 279                 return 0;
 280
 281         h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL);
 282         if (!h->htable)
 283                 return -ENOMEM;
 284
 285         h->nslot = nslot;
 286         h->mask = nslot - 1;
 287         return 0;
 288 }
 289
 290 int avtab_alloc(struct avtab *h, u32 nrules)
 291 {
 292         int rc;
 293         u32 nslot = 0;
 294
 295         if (nrules != 0) {
 296                 nslot = nrules > 3 ? rounddown_pow_of_two(nrules / 2) : 2;
 297                 if (nslot > MAX_AVTAB_HASH_BUCKETS)
 298                         nslot = MAX_AVTAB_HASH_BUCKETS;
 299
 300                 rc = avtab_alloc_common(h, nslot);
 301                 if (rc)
 302                         return rc;
 303         }
 304
 305         pr_debug("SELinux: %d avtab hash slots, %d rules.\n", nslot, nrules);
 306         return 0;
 307 }
 308
 309 int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
 310 {
 311         return avtab_alloc_common(new, orig->nslot);
 312 }
 313
 314 #ifdef CONFIG_SECURITY_SELINUX_DEBUG
 315 void avtab_hash_eval(struct avtab *h, const char *tag)
 316 {
 317         u32 i, chain_len, slots_used, max_chain_len;
 318         unsigned long long chain2_len_sum;
 319         struct avtab_node *cur;
 320
 321         slots_used = 0;
 322         max_chain_len = 0;
 323         chain2_len_sum = 0;
 324         for (i = 0; i < h->nslot; i++) {
 325                 cur = h->htable[i];
 326                 if (cur) {
 327                         slots_used++;
 328                         chain_len = 0;
 329                         while (cur) {
 330                                 chain_len++;
 331                                 cur = cur->next;
 332                         }
 333
 334                         if (chain_len > max_chain_len)
 335                                 max_chain_len = chain_len;
 336                         chain2_len_sum += (unsigned long long)chain_len * chain_len;
 337                 }
 338         }
 339
 340         pr_debug("SELinux: %s:  %d entries and %d/%d buckets used, "
 341                "longest chain length %d, sum of chain length^2 %llu\n",
 342                tag, h->nel, slots_used, h->nslot, max_chain_len,
 343                chain2_len_sum);
 344 }
 345 #endif /* CONFIG_SECURITY_SELINUX_DEBUG */
 346
 347 static const uint16_t spec_order[] = {
 348         AVTAB_ALLOWED,
 349         AVTAB_AUDITDENY,
 350         AVTAB_AUDITALLOW,
 351         AVTAB_TRANSITION,
 352         AVTAB_CHANGE,
 353         AVTAB_MEMBER,
 354         AVTAB_XPERMS_ALLOWED,
 355         AVTAB_XPERMS_AUDITALLOW,
 356         AVTAB_XPERMS_DONTAUDIT
 357 };
 358
 359 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 360                     int (*insertf)(struct avtab *a, const struct avtab_key *k,
 361                                    const struct avtab_datum *d, void *p),
 362                     void *p)
 363 {
 364         __le16 buf16[4];
 365         u16 enabled;
 366         u32 items, items2, val, i;
 367         struct avtab_key key;
 368         struct avtab_datum datum;
 369         struct avtab_extended_perms xperms;
 370         __le32 buf32[ARRAY_SIZE(xperms.perms.p)];
 371         int rc;
 372         unsigned int set, vers = pol->policyvers;
 373
 374         memset(&key, 0, sizeof(struct avtab_key));
 375         memset(&datum, 0, sizeof(struct avtab_datum));
 376
 377         if (vers < POLICYDB_VERSION_AVTAB) {
 378                 rc = next_entry(buf32, fp, sizeof(u32));
 379                 if (rc) {
 380                         pr_err("SELinux: avtab: truncated entry\n");
 381                         return rc;
 382                 }
 383                 items2 = le32_to_cpu(buf32[0]);
 384                 if (items2 > ARRAY_SIZE(buf32)) {
 385                         pr_err("SELinux: avtab: entry overflow\n");
 386                         return -EINVAL;
 387
 388                 }
 389                 rc = next_entry(buf32, fp, sizeof(u32)*items2);
 390                 if (rc) {
 391                         pr_err("SELinux: avtab: truncated entry\n");
 392                         return rc;
 393                 }
 394                 items = 0;
 395
 396                 val = le32_to_cpu(buf32[items++]);
 397                 key.source_type = (u16)val;
 398                 if (key.source_type != val) {
 399                         pr_err("SELinux: avtab: truncated source type\n");
 400                         return -EINVAL;
 401                 }
 402                 val = le32_to_cpu(buf32[items++]);
 403                 key.target_type = (u16)val;
 404                 if (key.target_type != val) {
 405                         pr_err("SELinux: avtab: truncated target type\n");
 406                         return -EINVAL;
 407                 }
 408                 val = le32_to_cpu(buf32[items++]);
 409                 key.target_class = (u16)val;
 410                 if (key.target_class != val) {
 411                         pr_err("SELinux: avtab: truncated target class\n");
 412                         return -EINVAL;
 413                 }
 414
 415                 val = le32_to_cpu(buf32[items++]);
 416                 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
 417
 418                 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
 419                         pr_err("SELinux: avtab: null entry\n");
 420                         return -EINVAL;
 421                 }
 422                 if ((val & AVTAB_AV) &&
 423                     (val & AVTAB_TYPE)) {
 424                         pr_err("SELinux: avtab: entry has both access vectors and types\n");
 425                         return -EINVAL;
 426                 }
 427                 if (val & AVTAB_XPERMS) {
 428                         pr_err("SELinux: avtab: entry has extended permissions\n");
 429                         return -EINVAL;
 430                 }
 431
 432                 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
 433                         if (val & spec_order[i]) {
 434                                 key.specified = spec_order[i] | enabled;
 435                                 datum.u.data = le32_to_cpu(buf32[items++]);
 436                                 rc = insertf(a, &key, &datum, p);
 437                                 if (rc)
 438                                         return rc;
 439                         }
 440                 }
 441
 442                 if (items != items2) {
 443                         pr_err("SELinux: avtab: entry only had %d items, expected %d\n",
 444                                items2, items);
 445                         return -EINVAL;
 446                 }
 447                 return 0;
 448         }
 449
 450         rc = next_entry(buf16, fp, sizeof(u16)*4);
 451         if (rc) {
 452                 pr_err("SELinux: avtab: truncated entry\n");
 453                 return rc;
 454         }
 455
 456         items = 0;
 457         key.source_type = le16_to_cpu(buf16[items++]);
 458         key.target_type = le16_to_cpu(buf16[items++]);
 459         key.target_class = le16_to_cpu(buf16[items++]);
 460         key.specified = le16_to_cpu(buf16[items++]);
 461
 462         if (!policydb_type_isvalid(pol, key.source_type) ||
 463             !policydb_type_isvalid(pol, key.target_type) ||
 464             !policydb_class_isvalid(pol, key.target_class)) {
 465                 pr_err("SELinux: avtab: invalid type or class\n");
 466                 return -EINVAL;
 467         }
 468
 469         set = hweight16(key.specified & (AVTAB_XPERMS | AVTAB_TYPE | AVTAB_AV));
 470         if (!set || set > 1) {
 471                 pr_err("SELinux:  avtab:  more than one specifier\n");
 472                 return -EINVAL;
 473         }
 474
 475         if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) &&
 476                         (key.specified & AVTAB_XPERMS)) {
 477                 pr_err("SELinux:  avtab:  policy version %u does not "
 478                                 "support extended permissions rules and one "
 479                                 "was specified\n", vers);
 480                 return -EINVAL;
 481         } else if (key.specified & AVTAB_XPERMS) {
 482                 memset(&xperms, 0, sizeof(struct avtab_extended_perms));
 483                 rc = next_entry(&xperms.specified, fp, sizeof(u8));
 484                 if (rc) {
 485                         pr_err("SELinux: avtab: truncated entry\n");
 486                         return rc;
 487                 }
 488                 rc = next_entry(&xperms.driver, fp, sizeof(u8));
 489                 if (rc) {
 490                         pr_err("SELinux: avtab: truncated entry\n");
 491                         return rc;
 492                 }
 493                 rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p));
 494                 if (rc) {
 495                         pr_err("SELinux: avtab: truncated entry\n");
 496                         return rc;
 497                 }
 498                 for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++)
 499                         xperms.perms.p[i] = le32_to_cpu(buf32[i]);
 500                 datum.u.xperms = &xperms;
 501         } else {
 502                 rc = next_entry(buf32, fp, sizeof(u32));
 503                 if (rc) {
 504                         pr_err("SELinux: avtab: truncated entry\n");
 505                         return rc;
 506                 }
 507                 datum.u.data = le32_to_cpu(*buf32);
 508         }
 509         if ((key.specified & AVTAB_TYPE) &&
 510             !policydb_type_isvalid(pol, datum.u.data)) {
 511                 pr_err("SELinux: avtab: invalid type\n");
 512                 return -EINVAL;
 513         }
 514         return insertf(a, &key, &datum, p);
 515 }
 516
 517 static int avtab_insertf(struct avtab *a, const struct avtab_key *k,
 518                          const struct avtab_datum *d, void *p)
 519 {
 520         return avtab_insert(a, k, d);
 521 }
 522
 523 int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
 524 {
 525         int rc;
 526         __le32 buf[1];
 527         u32 nel, i;
 528
 529
 530         rc = next_entry(buf, fp, sizeof(u32));
 531         if (rc < 0) {
 532                 pr_err("SELinux: avtab: truncated table\n");
 533                 goto bad;
 534         }
 535         nel = le32_to_cpu(buf[0]);
 536         if (!nel) {
 537                 pr_err("SELinux: avtab: table is empty\n");
 538                 rc = -EINVAL;
 539                 goto bad;
 540         }
 541
 542         rc = avtab_alloc(a, nel);
 543         if (rc)
 544                 goto bad;
 545
 546         for (i = 0; i < nel; i++) {
 547                 rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
 548                 if (rc) {
 549                         if (rc == -ENOMEM)
 550                                 pr_err("SELinux: avtab: out of memory\n");
 551                         else if (rc == -EEXIST)
 552                                 pr_err("SELinux: avtab: duplicate entry\n");
 553
 554                         goto bad;
 555                 }
 556         }
 557
 558         rc = 0;
 559 out:
 560         return rc;
 561
 562 bad:
 563         avtab_destroy(a);
 564         goto out;
 565 }
 566
 567 int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
 568 {
 569         __le16 buf16[4];
 570         __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)];
 571         int rc;
 572         unsigned int i;
 573
 574         buf16[0] = cpu_to_le16(cur->key.source_type);
 575         buf16[1] = cpu_to_le16(cur->key.target_type);
 576         buf16[2] = cpu_to_le16(cur->key.target_class);
 577         buf16[3] = cpu_to_le16(cur->key.specified);
 578         rc = put_entry(buf16, sizeof(u16), 4, fp);
 579         if (rc)
 580                 return rc;
 581
 582         if (cur->key.specified & AVTAB_XPERMS) {
 583                 rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp);
 584                 if (rc)
 585                         return rc;
 586                 rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp);
 587                 if (rc)
 588                         return rc;
 589                 for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++)
 590                         buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]);
 591                 rc = put_entry(buf32, sizeof(u32),
 592                                 ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp);
 593         } else {
 594                 buf32[0] = cpu_to_le32(cur->datum.u.data);
 595                 rc = put_entry(buf32, sizeof(u32), 1, fp);
 596         }
 597         if (rc)
 598                 return rc;
 599         return 0;
 600 }
 601
 602 int avtab_write(struct policydb *p, struct avtab *a, void *fp)
 603 {
 604         u32 i;
 605         int rc = 0;
 606         struct avtab_node *cur;
 607         __le32 buf[1];
 608
 609         buf[0] = cpu_to_le32(a->nel);
 610         rc = put_entry(buf, sizeof(u32), 1, fp);
 611         if (rc)
 612                 return rc;
 613
 614         for (i = 0; i < a->nslot; i++) {
 615                 for (cur = a->htable[i]; cur;
 616                      cur = cur->next) {
 617                         rc = avtab_write_item(p, cur, fp);
 618                         if (rc)
 619                                 return rc;
 620                 }
 621         }
 622
 623         return rc;
 624 }
 625
 626 void __init avtab_cache_init(void)
 627 {
 628         avtab_node_cachep = kmem_cache_create("avtab_node",
 629                                               sizeof(struct avtab_node),
 630                                               0, SLAB_PANIC, NULL);
 631         avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
 632                                                 sizeof(struct avtab_extended_perms),
 633                                                 0, SLAB_PANIC, NULL);
 634 }