linux/security/selinux/ss/avtab.c
<<
>>
Prefs
   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
  26static struct kmem_cache *avtab_node_cachep;
  27
  28static 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
  34static struct avtab_node*
  35avtab_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
  57static 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 */
  97struct avtab_node *
  98avtab_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
 128struct 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 */
 162struct avtab_node*
 163avtab_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
 193struct avtab_node*
 194avtab_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
 222void 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
 245int avtab_init(struct avtab *h)
 246{
 247        h->htable = NULL;
 248        h->nel = 0;
 249        return 0;
 250}
 251
 252int 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_HASH_BUCKETS)
 270                nslot = MAX_AVTAB_HASH_BUCKETS;
 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
 286void 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
 317static uint16_t spec_order[] = {
 318        AVTAB_ALLOWED,
 319        AVTAB_AUDITDENY,
 320        AVTAB_AUDITALLOW,
 321        AVTAB_TRANSITION,
 322        AVTAB_CHANGE,
 323        AVTAB_MEMBER
 324};
 325
 326int 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) {
 346                        printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 347                        return rc;
 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 -EINVAL;
 353
 354                }
 355                rc = next_entry(buf32, fp, sizeof(u32)*items2);
 356                if (rc) {
 357                        printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 358                        return rc;
 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 -EINVAL;
 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 -EINVAL;
 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 -EINVAL;
 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 -EINVAL;
 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 -EINVAL;
 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 -EINVAL;
 407                }
 408                return 0;
 409        }
 410
 411        rc = next_entry(buf16, fp, sizeof(u16)*4);
 412        if (rc) {
 413                printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 414                return rc;
 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 -EINVAL;
 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 -EINVAL;
 438        }
 439
 440        rc = next_entry(buf32, fp, sizeof(u32));
 441        if (rc) {
 442                printk(KERN_ERR "SELinux: avtab: truncated entry\n");
 443                return rc;
 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 -EINVAL;
 450        }
 451        return insertf(a, &key, &datum, p);
 452}
 453
 454static 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
 460int 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
 491                        goto bad;
 492                }
 493        }
 494
 495        rc = 0;
 496out:
 497        return rc;
 498
 499bad:
 500        avtab_destroy(a);
 501        goto out;
 502}
 503
 504int avtab_write_item(struct policydb *p, struct avtab_node *cur, void *fp)
 505{
 506        __le16 buf16[4];
 507        __le32 buf32[1];
 508        int rc;
 509
 510        buf16[0] = cpu_to_le16(cur->key.source_type);
 511        buf16[1] = cpu_to_le16(cur->key.target_type);
 512        buf16[2] = cpu_to_le16(cur->key.target_class);
 513        buf16[3] = cpu_to_le16(cur->key.specified);
 514        rc = put_entry(buf16, sizeof(u16), 4, fp);
 515        if (rc)
 516                return rc;
 517        buf32[0] = cpu_to_le32(cur->datum.data);
 518        rc = put_entry(buf32, sizeof(u32), 1, fp);
 519        if (rc)
 520                return rc;
 521        return 0;
 522}
 523
 524int avtab_write(struct policydb *p, struct avtab *a, void *fp)
 525{
 526        unsigned int i;
 527        int rc = 0;
 528        struct avtab_node *cur;
 529        __le32 buf[1];
 530
 531        buf[0] = cpu_to_le32(a->nel);
 532        rc = put_entry(buf, sizeof(u32), 1, fp);
 533        if (rc)
 534                return rc;
 535
 536        for (i = 0; i < a->nslot; i++) {
 537                for (cur = a->htable[i]; cur; cur = cur->next) {
 538                        rc = avtab_write_item(p, cur, fp);
 539                        if (rc)
 540                                return rc;
 541                }
 542        }
 543
 544        return rc;
 545}
 546void avtab_cache_init(void)
 547{
 548        avtab_node_cachep = kmem_cache_create("avtab_node",
 549                                              sizeof(struct avtab_node),
 550                                              0, SLAB_PANIC, NULL);
 551}
 552
 553void avtab_cache_destroy(void)
 554{
 555        kmem_cache_destroy(avtab_node_cachep);
 556}
 557