0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020 #include <linux/kernel.h>
0021 #include <linux/slab.h>
0022 #include <linux/errno.h>
0023 #include "avtab.h"
0024 #include "policydb.h"
0025
0026 static struct kmem_cache *avtab_node_cachep __ro_after_init;
0027 static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
0028
0029
0030
0031
0032 static inline int avtab_hash(const struct avtab_key *keyp, u32 mask)
0033 {
0034 static const u32 c1 = 0xcc9e2d51;
0035 static const u32 c2 = 0x1b873593;
0036 static const u32 r1 = 15;
0037 static const u32 r2 = 13;
0038 static const u32 m = 5;
0039 static const u32 n = 0xe6546b64;
0040
0041 u32 hash = 0;
0042
0043 #define mix(input) do { \
0044 u32 v = input; \
0045 v *= c1; \
0046 v = (v << r1) | (v >> (32 - r1)); \
0047 v *= c2; \
0048 hash ^= v; \
0049 hash = (hash << r2) | (hash >> (32 - r2)); \
0050 hash = hash * m + n; \
0051 } while (0)
0052
0053 mix(keyp->target_class);
0054 mix(keyp->target_type);
0055 mix(keyp->source_type);
0056
0057 #undef mix
0058
0059 hash ^= hash >> 16;
0060 hash *= 0x85ebca6b;
0061 hash ^= hash >> 13;
0062 hash *= 0xc2b2ae35;
0063 hash ^= hash >> 16;
0064
0065 return hash & mask;
0066 }
0067
0068 static struct avtab_node*
0069 avtab_insert_node(struct avtab *h, int hvalue,
0070 struct avtab_node *prev,
0071 const struct avtab_key *key, const struct avtab_datum *datum)
0072 {
0073 struct avtab_node *newnode;
0074 struct avtab_extended_perms *xperms;
0075 newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
0076 if (newnode == NULL)
0077 return NULL;
0078 newnode->key = *key;
0079
0080 if (key->specified & AVTAB_XPERMS) {
0081 xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL);
0082 if (xperms == NULL) {
0083 kmem_cache_free(avtab_node_cachep, newnode);
0084 return NULL;
0085 }
0086 *xperms = *(datum->u.xperms);
0087 newnode->datum.u.xperms = xperms;
0088 } else {
0089 newnode->datum.u.data = datum->u.data;
0090 }
0091
0092 if (prev) {
0093 newnode->next = prev->next;
0094 prev->next = newnode;
0095 } else {
0096 struct avtab_node **n = &h->htable[hvalue];
0097
0098 newnode->next = *n;
0099 *n = newnode;
0100 }
0101
0102 h->nel++;
0103 return newnode;
0104 }
0105
0106 static int avtab_insert(struct avtab *h, const struct avtab_key *key,
0107 const struct avtab_datum *datum)
0108 {
0109 int hvalue;
0110 struct avtab_node *prev, *cur, *newnode;
0111 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
0112
0113 if (!h || !h->nslot)
0114 return -EINVAL;
0115
0116 hvalue = avtab_hash(key, h->mask);
0117 for (prev = NULL, cur = h->htable[hvalue];
0118 cur;
0119 prev = cur, cur = cur->next) {
0120 if (key->source_type == cur->key.source_type &&
0121 key->target_type == cur->key.target_type &&
0122 key->target_class == cur->key.target_class &&
0123 (specified & cur->key.specified)) {
0124
0125 if (specified & AVTAB_XPERMS)
0126 break;
0127 return -EEXIST;
0128 }
0129 if (key->source_type < cur->key.source_type)
0130 break;
0131 if (key->source_type == cur->key.source_type &&
0132 key->target_type < cur->key.target_type)
0133 break;
0134 if (key->source_type == cur->key.source_type &&
0135 key->target_type == cur->key.target_type &&
0136 key->target_class < cur->key.target_class)
0137 break;
0138 }
0139
0140 newnode = avtab_insert_node(h, hvalue, prev, key, datum);
0141 if (!newnode)
0142 return -ENOMEM;
0143
0144 return 0;
0145 }
0146
0147
0148
0149
0150
0151 struct avtab_node *avtab_insert_nonunique(struct avtab *h,
0152 const struct avtab_key *key,
0153 const struct avtab_datum *datum)
0154 {
0155 int hvalue;
0156 struct avtab_node *prev, *cur;
0157 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
0158
0159 if (!h || !h->nslot)
0160 return NULL;
0161 hvalue = avtab_hash(key, h->mask);
0162 for (prev = NULL, cur = h->htable[hvalue];
0163 cur;
0164 prev = cur, cur = cur->next) {
0165 if (key->source_type == cur->key.source_type &&
0166 key->target_type == cur->key.target_type &&
0167 key->target_class == cur->key.target_class &&
0168 (specified & cur->key.specified))
0169 break;
0170 if (key->source_type < cur->key.source_type)
0171 break;
0172 if (key->source_type == cur->key.source_type &&
0173 key->target_type < cur->key.target_type)
0174 break;
0175 if (key->source_type == cur->key.source_type &&
0176 key->target_type == cur->key.target_type &&
0177 key->target_class < cur->key.target_class)
0178 break;
0179 }
0180 return avtab_insert_node(h, hvalue, prev, key, datum);
0181 }
0182
0183 struct avtab_datum *avtab_search(struct avtab *h, const struct avtab_key *key)
0184 {
0185 int hvalue;
0186 struct avtab_node *cur;
0187 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
0188
0189 if (!h || !h->nslot)
0190 return NULL;
0191
0192 hvalue = avtab_hash(key, h->mask);
0193 for (cur = h->htable[hvalue]; cur;
0194 cur = cur->next) {
0195 if (key->source_type == cur->key.source_type &&
0196 key->target_type == cur->key.target_type &&
0197 key->target_class == cur->key.target_class &&
0198 (specified & cur->key.specified))
0199 return &cur->datum;
0200
0201 if (key->source_type < cur->key.source_type)
0202 break;
0203 if (key->source_type == cur->key.source_type &&
0204 key->target_type < cur->key.target_type)
0205 break;
0206 if (key->source_type == cur->key.source_type &&
0207 key->target_type == cur->key.target_type &&
0208 key->target_class < cur->key.target_class)
0209 break;
0210 }
0211
0212 return NULL;
0213 }
0214
0215
0216
0217
0218 struct avtab_node *avtab_search_node(struct avtab *h,
0219 const struct avtab_key *key)
0220 {
0221 int hvalue;
0222 struct avtab_node *cur;
0223 u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
0224
0225 if (!h || !h->nslot)
0226 return NULL;
0227
0228 hvalue = avtab_hash(key, h->mask);
0229 for (cur = h->htable[hvalue]; cur;
0230 cur = cur->next) {
0231 if (key->source_type == cur->key.source_type &&
0232 key->target_type == cur->key.target_type &&
0233 key->target_class == cur->key.target_class &&
0234 (specified & cur->key.specified))
0235 return cur;
0236
0237 if (key->source_type < cur->key.source_type)
0238 break;
0239 if (key->source_type == cur->key.source_type &&
0240 key->target_type < cur->key.target_type)
0241 break;
0242 if (key->source_type == cur->key.source_type &&
0243 key->target_type == cur->key.target_type &&
0244 key->target_class < cur->key.target_class)
0245 break;
0246 }
0247 return NULL;
0248 }
0249
0250 struct avtab_node*
0251 avtab_search_node_next(struct avtab_node *node, int specified)
0252 {
0253 struct avtab_node *cur;
0254
0255 if (!node)
0256 return NULL;
0257
0258 specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
0259 for (cur = node->next; cur; cur = cur->next) {
0260 if (node->key.source_type == cur->key.source_type &&
0261 node->key.target_type == cur->key.target_type &&
0262 node->key.target_class == cur->key.target_class &&
0263 (specified & cur->key.specified))
0264 return cur;
0265
0266 if (node->key.source_type < cur->key.source_type)
0267 break;
0268 if (node->key.source_type == cur->key.source_type &&
0269 node->key.target_type < cur->key.target_type)
0270 break;
0271 if (node->key.source_type == cur->key.source_type &&
0272 node->key.target_type == cur->key.target_type &&
0273 node->key.target_class < cur->key.target_class)
0274 break;
0275 }
0276 return NULL;
0277 }
0278
0279 void avtab_destroy(struct avtab *h)
0280 {
0281 int i;
0282 struct avtab_node *cur, *temp;
0283
0284 if (!h)
0285 return;
0286
0287 for (i = 0; i < h->nslot; i++) {
0288 cur = h->htable[i];
0289 while (cur) {
0290 temp = cur;
0291 cur = cur->next;
0292 if (temp->key.specified & AVTAB_XPERMS)
0293 kmem_cache_free(avtab_xperms_cachep,
0294 temp->datum.u.xperms);
0295 kmem_cache_free(avtab_node_cachep, temp);
0296 }
0297 }
0298 kvfree(h->htable);
0299 h->htable = NULL;
0300 h->nel = 0;
0301 h->nslot = 0;
0302 h->mask = 0;
0303 }
0304
0305 void avtab_init(struct avtab *h)
0306 {
0307 h->htable = NULL;
0308 h->nel = 0;
0309 h->nslot = 0;
0310 h->mask = 0;
0311 }
0312
0313 static int avtab_alloc_common(struct avtab *h, u32 nslot)
0314 {
0315 if (!nslot)
0316 return 0;
0317
0318 h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL);
0319 if (!h->htable)
0320 return -ENOMEM;
0321
0322 h->nslot = nslot;
0323 h->mask = nslot - 1;
0324 return 0;
0325 }
0326
0327 int avtab_alloc(struct avtab *h, u32 nrules)
0328 {
0329 int rc;
0330 u32 nslot = 0;
0331
0332 if (nrules != 0) {
0333 u32 shift = 1;
0334 u32 work = nrules >> 3;
0335 while (work) {
0336 work >>= 1;
0337 shift++;
0338 }
0339 nslot = 1 << shift;
0340 if (nslot > MAX_AVTAB_HASH_BUCKETS)
0341 nslot = MAX_AVTAB_HASH_BUCKETS;
0342
0343 rc = avtab_alloc_common(h, nslot);
0344 if (rc)
0345 return rc;
0346 }
0347
0348 pr_debug("SELinux: %d avtab hash slots, %d rules.\n", nslot, nrules);
0349 return 0;
0350 }
0351
0352 int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
0353 {
0354 return avtab_alloc_common(new, orig->nslot);
0355 }
0356
0357 void avtab_hash_eval(struct avtab *h, char *tag)
0358 {
0359 int i, chain_len, slots_used, max_chain_len;
0360 unsigned long long chain2_len_sum;
0361 struct avtab_node *cur;
0362
0363 slots_used = 0;
0364 max_chain_len = 0;
0365 chain2_len_sum = 0;
0366 for (i = 0; i < h->nslot; i++) {
0367 cur = h->htable[i];
0368 if (cur) {
0369 slots_used++;
0370 chain_len = 0;
0371 while (cur) {
0372 chain_len++;
0373 cur = cur->next;
0374 }
0375
0376 if (chain_len > max_chain_len)
0377 max_chain_len = chain_len;
0378 chain2_len_sum += chain_len * chain_len;
0379 }
0380 }
0381
0382 pr_debug("SELinux: %s: %d entries and %d/%d buckets used, "
0383 "longest chain length %d sum of chain length^2 %llu\n",
0384 tag, h->nel, slots_used, h->nslot, max_chain_len,
0385 chain2_len_sum);
0386 }
0387
0388 static const uint16_t spec_order[] = {
0389 AVTAB_ALLOWED,
0390 AVTAB_AUDITDENY,
0391 AVTAB_AUDITALLOW,
0392 AVTAB_TRANSITION,
0393 AVTAB_CHANGE,
0394 AVTAB_MEMBER,
0395 AVTAB_XPERMS_ALLOWED,
0396 AVTAB_XPERMS_AUDITALLOW,
0397 AVTAB_XPERMS_DONTAUDIT
0398 };
0399
0400 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
0401 int (*insertf)(struct avtab *a, const struct avtab_key *k,
0402 const struct avtab_datum *d, void *p),
0403 void *p)
0404 {
0405 __le16 buf16[4];
0406 u16 enabled;
0407 u32 items, items2, val, vers = pol->policyvers;
0408 struct avtab_key key;
0409 struct avtab_datum datum;
0410 struct avtab_extended_perms xperms;
0411 __le32 buf32[ARRAY_SIZE(xperms.perms.p)];
0412 int i, rc;
0413 unsigned set;
0414
0415 memset(&key, 0, sizeof(struct avtab_key));
0416 memset(&datum, 0, sizeof(struct avtab_datum));
0417
0418 if (vers < POLICYDB_VERSION_AVTAB) {
0419 rc = next_entry(buf32, fp, sizeof(u32));
0420 if (rc) {
0421 pr_err("SELinux: avtab: truncated entry\n");
0422 return rc;
0423 }
0424 items2 = le32_to_cpu(buf32[0]);
0425 if (items2 > ARRAY_SIZE(buf32)) {
0426 pr_err("SELinux: avtab: entry overflow\n");
0427 return -EINVAL;
0428
0429 }
0430 rc = next_entry(buf32, fp, sizeof(u32)*items2);
0431 if (rc) {
0432 pr_err("SELinux: avtab: truncated entry\n");
0433 return rc;
0434 }
0435 items = 0;
0436
0437 val = le32_to_cpu(buf32[items++]);
0438 key.source_type = (u16)val;
0439 if (key.source_type != val) {
0440 pr_err("SELinux: avtab: truncated source type\n");
0441 return -EINVAL;
0442 }
0443 val = le32_to_cpu(buf32[items++]);
0444 key.target_type = (u16)val;
0445 if (key.target_type != val) {
0446 pr_err("SELinux: avtab: truncated target type\n");
0447 return -EINVAL;
0448 }
0449 val = le32_to_cpu(buf32[items++]);
0450 key.target_class = (u16)val;
0451 if (key.target_class != val) {
0452 pr_err("SELinux: avtab: truncated target class\n");
0453 return -EINVAL;
0454 }
0455
0456 val = le32_to_cpu(buf32[items++]);
0457 enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
0458
0459 if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
0460 pr_err("SELinux: avtab: null entry\n");
0461 return -EINVAL;
0462 }
0463 if ((val & AVTAB_AV) &&
0464 (val & AVTAB_TYPE)) {
0465 pr_err("SELinux: avtab: entry has both access vectors and types\n");
0466 return -EINVAL;
0467 }
0468 if (val & AVTAB_XPERMS) {
0469 pr_err("SELinux: avtab: entry has extended permissions\n");
0470 return -EINVAL;
0471 }
0472
0473 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
0474 if (val & spec_order[i]) {
0475 key.specified = spec_order[i] | enabled;
0476 datum.u.data = le32_to_cpu(buf32[items++]);
0477 rc = insertf(a, &key, &datum, p);
0478 if (rc)
0479 return rc;
0480 }
0481 }
0482
0483 if (items != items2) {
0484 pr_err("SELinux: avtab: entry only had %d items, expected %d\n",
0485 items2, items);
0486 return -EINVAL;
0487 }
0488 return 0;
0489 }
0490
0491 rc = next_entry(buf16, fp, sizeof(u16)*4);
0492 if (rc) {
0493 pr_err("SELinux: avtab: truncated entry\n");
0494 return rc;
0495 }
0496
0497 items = 0;
0498 key.source_type = le16_to_cpu(buf16[items++]);
0499 key.target_type = le16_to_cpu(buf16[items++]);
0500 key.target_class = le16_to_cpu(buf16[items++]);
0501 key.specified = le16_to_cpu(buf16[items++]);
0502
0503 if (!policydb_type_isvalid(pol, key.source_type) ||
0504 !policydb_type_isvalid(pol, key.target_type) ||
0505 !policydb_class_isvalid(pol, key.target_class)) {
0506 pr_err("SELinux: avtab: invalid type or class\n");
0507 return -EINVAL;
0508 }
0509
0510 set = 0;
0511 for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
0512 if (key.specified & spec_order[i])
0513 set++;
0514 }
0515 if (!set || set > 1) {
0516 pr_err("SELinux: avtab: more than one specifier\n");
0517 return -EINVAL;
0518 }
0519
0520 if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) &&
0521 (key.specified & AVTAB_XPERMS)) {
0522 pr_err("SELinux: avtab: policy version %u does not "
0523 "support extended permissions rules and one "
0524 "was specified\n", vers);
0525 return -EINVAL;
0526 } else if (key.specified & AVTAB_XPERMS) {
0527 memset(&xperms, 0, sizeof(struct avtab_extended_perms));
0528 rc = next_entry(&xperms.specified, fp, sizeof(u8));
0529 if (rc) {
0530 pr_err("SELinux: avtab: truncated entry\n");
0531 return rc;
0532 }
0533 rc = next_entry(&xperms.driver, fp, sizeof(u8));
0534 if (rc) {
0535 pr_err("SELinux: avtab: truncated entry\n");
0536 return rc;
0537 }
0538 rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p));
0539 if (rc) {
0540 pr_err("SELinux: avtab: truncated entry\n");
0541 return rc;
0542 }
0543 for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++)
0544 xperms.perms.p[i] = le32_to_cpu(buf32[i]);
0545 datum.u.xperms = &xperms;
0546 } else {
0547 rc = next_entry(buf32, fp, sizeof(u32));
0548 if (rc) {
0549 pr_err("SELinux: avtab: truncated entry\n");
0550 return rc;
0551 }
0552 datum.u.data = le32_to_cpu(*buf32);
0553 }
0554 if ((key.specified & AVTAB_TYPE) &&
0555 !policydb_type_isvalid(pol, datum.u.data)) {
0556 pr_err("SELinux: avtab: invalid type\n");
0557 return -EINVAL;
0558 }
0559 return insertf(a, &key, &datum, p);
0560 }
0561
0562 static int avtab_insertf(struct avtab *a, const struct avtab_key *k,
0563 const struct avtab_datum *d, void *p)
0564 {
0565 return avtab_insert(a, k, d);
0566 }
0567
0568 int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
0569 {
0570 int rc;
0571 __le32 buf[1];
0572 u32 nel, i;
0573
0574
0575 rc = next_entry(buf, fp, sizeof(u32));
0576 if (rc < 0) {
0577 pr_err("SELinux: avtab: truncated table\n");
0578 goto bad;
0579 }
0580 nel = le32_to_cpu(buf[0]);
0581 if (!nel) {
0582 pr_err("SELinux: avtab: table is empty\n");
0583 rc = -EINVAL;
0584 goto bad;
0585 }
0586
0587 rc = avtab_alloc(a, nel);
0588 if (rc)
0589 goto bad;
0590
0591 for (i = 0; i < nel; i++) {
0592 rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
0593 if (rc) {
0594 if (rc == -ENOMEM)
0595 pr_err("SELinux: avtab: out of memory\n");
0596 else if (rc == -EEXIST)
0597 pr_err("SELinux: avtab: duplicate entry\n");
0598
0599 goto bad;
0600 }
0601 }
0602
0603 rc = 0;
0604 out:
0605 return rc;
0606
0607 bad:
0608 avtab_destroy(a);
0609 goto out;
0610 }
0611
0612 int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
0613 {
0614 __le16 buf16[4];
0615 __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)];
0616 int rc;
0617 unsigned int i;
0618
0619 buf16[0] = cpu_to_le16(cur->key.source_type);
0620 buf16[1] = cpu_to_le16(cur->key.target_type);
0621 buf16[2] = cpu_to_le16(cur->key.target_class);
0622 buf16[3] = cpu_to_le16(cur->key.specified);
0623 rc = put_entry(buf16, sizeof(u16), 4, fp);
0624 if (rc)
0625 return rc;
0626
0627 if (cur->key.specified & AVTAB_XPERMS) {
0628 rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp);
0629 if (rc)
0630 return rc;
0631 rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp);
0632 if (rc)
0633 return rc;
0634 for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++)
0635 buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]);
0636 rc = put_entry(buf32, sizeof(u32),
0637 ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp);
0638 } else {
0639 buf32[0] = cpu_to_le32(cur->datum.u.data);
0640 rc = put_entry(buf32, sizeof(u32), 1, fp);
0641 }
0642 if (rc)
0643 return rc;
0644 return 0;
0645 }
0646
0647 int avtab_write(struct policydb *p, struct avtab *a, void *fp)
0648 {
0649 unsigned int i;
0650 int rc = 0;
0651 struct avtab_node *cur;
0652 __le32 buf[1];
0653
0654 buf[0] = cpu_to_le32(a->nel);
0655 rc = put_entry(buf, sizeof(u32), 1, fp);
0656 if (rc)
0657 return rc;
0658
0659 for (i = 0; i < a->nslot; i++) {
0660 for (cur = a->htable[i]; cur;
0661 cur = cur->next) {
0662 rc = avtab_write_item(p, cur, fp);
0663 if (rc)
0664 return rc;
0665 }
0666 }
0667
0668 return rc;
0669 }
0670
0671 void __init avtab_cache_init(void)
0672 {
0673 avtab_node_cachep = kmem_cache_create("avtab_node",
0674 sizeof(struct avtab_node),
0675 0, SLAB_PANIC, NULL);
0676 avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
0677 sizeof(struct avtab_extended_perms),
0678 0, SLAB_PANIC, NULL);
0679 }