security/selinux/ss/avtab.c

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