11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * Implementation of the access vector table type. 31da177e4SLinus Torvalds * 47efbb60bSStephen Smalley * Author : Stephen Smalley, <sds@tycho.nsa.gov> 51da177e4SLinus Torvalds */ 61da177e4SLinus Torvalds 71da177e4SLinus Torvalds /* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com> 81da177e4SLinus Torvalds * 91da177e4SLinus Torvalds * Added conditional policy language extensions 101da177e4SLinus Torvalds * 111da177e4SLinus Torvalds * Copyright (C) 2003 Tresys Technology, LLC 121da177e4SLinus Torvalds * This program is free software; you can redistribute it and/or modify 131da177e4SLinus Torvalds * it under the terms of the GNU General Public License as published by 141da177e4SLinus Torvalds * the Free Software Foundation, version 2. 153232c110SYuichi Nakamura * 163232c110SYuichi Nakamura * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp> 173232c110SYuichi Nakamura * Tuned number of hash slots for avtab to reduce memory usage 181da177e4SLinus Torvalds */ 191da177e4SLinus Torvalds 201da177e4SLinus Torvalds #include <linux/kernel.h> 211da177e4SLinus Torvalds #include <linux/slab.h> 221da177e4SLinus Torvalds #include <linux/errno.h> 231da177e4SLinus Torvalds #include "avtab.h" 241da177e4SLinus Torvalds #include "policydb.h" 251da177e4SLinus Torvalds 26cd2bb4cbSOndrej Mosnacek static struct kmem_cache *avtab_node_cachep __ro_after_init; 27cd2bb4cbSOndrej Mosnacek static struct kmem_cache *avtab_xperms_cachep __ro_after_init; 281da177e4SLinus Torvalds 2933ebc193SJohn Brooks /* Based on MurmurHash3, written by Austin Appleby and placed in the 3033ebc193SJohn Brooks * public domain. 3133ebc193SJohn Brooks */ 32e1cce3a3SOndrej Mosnacek static inline int avtab_hash(const struct avtab_key *keyp, u32 mask) 333232c110SYuichi Nakamura { 3433ebc193SJohn Brooks static const u32 c1 = 0xcc9e2d51; 3533ebc193SJohn Brooks static const u32 c2 = 0x1b873593; 3633ebc193SJohn Brooks static const u32 r1 = 15; 3733ebc193SJohn Brooks static const u32 r2 = 13; 3833ebc193SJohn Brooks static const u32 m = 5; 3933ebc193SJohn Brooks static const u32 n = 0xe6546b64; 4033ebc193SJohn Brooks 4133ebc193SJohn Brooks u32 hash = 0; 4233ebc193SJohn Brooks 4333ebc193SJohn Brooks #define mix(input) { \ 4433ebc193SJohn Brooks u32 v = input; \ 4533ebc193SJohn Brooks v *= c1; \ 4633ebc193SJohn Brooks v = (v << r1) | (v >> (32 - r1)); \ 4733ebc193SJohn Brooks v *= c2; \ 4833ebc193SJohn Brooks hash ^= v; \ 4933ebc193SJohn Brooks hash = (hash << r2) | (hash >> (32 - r2)); \ 5033ebc193SJohn Brooks hash = hash * m + n; \ 5133ebc193SJohn Brooks } 5233ebc193SJohn Brooks 5333ebc193SJohn Brooks mix(keyp->target_class); 5433ebc193SJohn Brooks mix(keyp->target_type); 5533ebc193SJohn Brooks mix(keyp->source_type); 5633ebc193SJohn Brooks 5733ebc193SJohn Brooks #undef mix 5833ebc193SJohn Brooks 5933ebc193SJohn Brooks hash ^= hash >> 16; 6033ebc193SJohn Brooks hash *= 0x85ebca6b; 6133ebc193SJohn Brooks hash ^= hash >> 13; 6233ebc193SJohn Brooks hash *= 0xc2b2ae35; 6333ebc193SJohn Brooks hash ^= hash >> 16; 6433ebc193SJohn Brooks 6533ebc193SJohn Brooks return hash & mask; 663232c110SYuichi Nakamura } 673232c110SYuichi Nakamura 681da177e4SLinus Torvalds static struct avtab_node* 691da177e4SLinus Torvalds avtab_insert_node(struct avtab *h, int hvalue, 70*056945a9SChristian Göttsche struct avtab_node *prev, 71e1cce3a3SOndrej Mosnacek const struct avtab_key *key, const struct avtab_datum *datum) 721da177e4SLinus Torvalds { 731da177e4SLinus Torvalds struct avtab_node *newnode; 74fa1aa143SJeff Vander Stoep struct avtab_extended_perms *xperms; 75c3762229SRobert P. J. Day newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); 761da177e4SLinus Torvalds if (newnode == NULL) 771da177e4SLinus Torvalds return NULL; 781da177e4SLinus Torvalds newnode->key = *key; 79fa1aa143SJeff Vander Stoep 80fa1aa143SJeff Vander Stoep if (key->specified & AVTAB_XPERMS) { 81fa1aa143SJeff Vander Stoep xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL); 82fa1aa143SJeff Vander Stoep if (xperms == NULL) { 83fa1aa143SJeff Vander Stoep kmem_cache_free(avtab_node_cachep, newnode); 84fa1aa143SJeff Vander Stoep return NULL; 85fa1aa143SJeff Vander Stoep } 86fa1aa143SJeff Vander Stoep *xperms = *(datum->u.xperms); 87fa1aa143SJeff Vander Stoep newnode->datum.u.xperms = xperms; 88fa1aa143SJeff Vander Stoep } else { 89fa1aa143SJeff Vander Stoep newnode->datum.u.data = datum->u.data; 90fa1aa143SJeff Vander Stoep } 91fa1aa143SJeff Vander Stoep 921da177e4SLinus Torvalds if (prev) { 931da177e4SLinus Torvalds newnode->next = prev->next; 941da177e4SLinus Torvalds prev->next = newnode; 951da177e4SLinus Torvalds } else { 96acdf52d9SKent Overstreet struct avtab_node **n = &h->htable[hvalue]; 97acdf52d9SKent Overstreet 98acdf52d9SKent Overstreet newnode->next = *n; 99acdf52d9SKent Overstreet *n = newnode; 1001da177e4SLinus Torvalds } 1011da177e4SLinus Torvalds 1021da177e4SLinus Torvalds h->nel++; 1031da177e4SLinus Torvalds return newnode; 1041da177e4SLinus Torvalds } 1051da177e4SLinus Torvalds 106e1cce3a3SOndrej Mosnacek static int avtab_insert(struct avtab *h, const struct avtab_key *key, 107e1cce3a3SOndrej Mosnacek const struct avtab_datum *datum) 1081da177e4SLinus Torvalds { 1091da177e4SLinus Torvalds int hvalue; 1101da177e4SLinus Torvalds struct avtab_node *prev, *cur, *newnode; 111782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 1121da177e4SLinus Torvalds 113442dc00fSOndrej Mosnacek if (!h || !h->nslot) 1141da177e4SLinus Torvalds return -EINVAL; 1151da177e4SLinus Torvalds 1163232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 117acdf52d9SKent Overstreet for (prev = NULL, cur = h->htable[hvalue]; 1181da177e4SLinus Torvalds cur; 1191da177e4SLinus Torvalds prev = cur, cur = cur->next) { 1201da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1211da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1221da177e4SLinus Torvalds key->target_class == cur->key.target_class && 123fa1aa143SJeff Vander Stoep (specified & cur->key.specified)) { 124fa1aa143SJeff Vander Stoep /* extended perms may not be unique */ 125fa1aa143SJeff Vander Stoep if (specified & AVTAB_XPERMS) 126fa1aa143SJeff Vander Stoep break; 1271da177e4SLinus Torvalds return -EEXIST; 128fa1aa143SJeff Vander Stoep } 1291da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 1301da177e4SLinus Torvalds break; 1311da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1321da177e4SLinus Torvalds key->target_type < cur->key.target_type) 1331da177e4SLinus Torvalds break; 1341da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1351da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1361da177e4SLinus Torvalds key->target_class < cur->key.target_class) 1371da177e4SLinus Torvalds break; 1381da177e4SLinus Torvalds } 1391da177e4SLinus Torvalds 140*056945a9SChristian Göttsche newnode = avtab_insert_node(h, hvalue, prev, key, datum); 1411da177e4SLinus Torvalds if (!newnode) 1421da177e4SLinus Torvalds return -ENOMEM; 1431da177e4SLinus Torvalds 1441da177e4SLinus Torvalds return 0; 1451da177e4SLinus Torvalds } 1461da177e4SLinus Torvalds 1471da177e4SLinus Torvalds /* Unlike avtab_insert(), this function allow multiple insertions of the same 1481da177e4SLinus Torvalds * key/specified mask into the table, as needed by the conditional avtab. 1491da177e4SLinus Torvalds * It also returns a pointer to the node inserted. 1501da177e4SLinus Torvalds */ 151e1cce3a3SOndrej Mosnacek struct avtab_node *avtab_insert_nonunique(struct avtab *h, 152e1cce3a3SOndrej Mosnacek const struct avtab_key *key, 153e1cce3a3SOndrej Mosnacek const struct avtab_datum *datum) 1541da177e4SLinus Torvalds { 1551da177e4SLinus Torvalds int hvalue; 1560c0e186fSVesa-Matti J Kari struct avtab_node *prev, *cur; 157782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 1581da177e4SLinus Torvalds 159442dc00fSOndrej Mosnacek if (!h || !h->nslot) 1601da177e4SLinus Torvalds return NULL; 1613232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 162acdf52d9SKent Overstreet for (prev = NULL, cur = h->htable[hvalue]; 1631da177e4SLinus Torvalds cur; 1641da177e4SLinus Torvalds prev = cur, cur = cur->next) { 1651da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1661da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1671da177e4SLinus Torvalds key->target_class == cur->key.target_class && 168782ebb99SStephen Smalley (specified & cur->key.specified)) 1691da177e4SLinus Torvalds break; 1701da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 1711da177e4SLinus Torvalds break; 1721da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1731da177e4SLinus Torvalds key->target_type < cur->key.target_type) 1741da177e4SLinus Torvalds break; 1751da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1761da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1771da177e4SLinus Torvalds key->target_class < cur->key.target_class) 1781da177e4SLinus Torvalds break; 1791da177e4SLinus Torvalds } 180*056945a9SChristian Göttsche return avtab_insert_node(h, hvalue, prev, key, datum); 1811da177e4SLinus Torvalds } 1821da177e4SLinus Torvalds 183e1cce3a3SOndrej Mosnacek struct avtab_datum *avtab_search(struct avtab *h, const struct avtab_key *key) 1841da177e4SLinus Torvalds { 1851da177e4SLinus Torvalds int hvalue; 1861da177e4SLinus Torvalds struct avtab_node *cur; 187782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 1881da177e4SLinus Torvalds 189442dc00fSOndrej Mosnacek if (!h || !h->nslot) 1901da177e4SLinus Torvalds return NULL; 1911da177e4SLinus Torvalds 1923232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 193acdf52d9SKent Overstreet for (cur = h->htable[hvalue]; cur; 194ba39db6eSStephen Smalley cur = cur->next) { 1951da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1961da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1971da177e4SLinus Torvalds key->target_class == cur->key.target_class && 198782ebb99SStephen Smalley (specified & cur->key.specified)) 1991da177e4SLinus Torvalds return &cur->datum; 2001da177e4SLinus Torvalds 2011da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 2021da177e4SLinus Torvalds break; 2031da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2041da177e4SLinus Torvalds key->target_type < cur->key.target_type) 2051da177e4SLinus Torvalds break; 2061da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2071da177e4SLinus Torvalds key->target_type == cur->key.target_type && 2081da177e4SLinus Torvalds key->target_class < cur->key.target_class) 2091da177e4SLinus Torvalds break; 2101da177e4SLinus Torvalds } 2111da177e4SLinus Torvalds 2121da177e4SLinus Torvalds return NULL; 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds 2151da177e4SLinus Torvalds /* This search function returns a node pointer, and can be used in 2161da177e4SLinus Torvalds * conjunction with avtab_search_next_node() 2171da177e4SLinus Torvalds */ 218e1cce3a3SOndrej Mosnacek struct avtab_node *avtab_search_node(struct avtab *h, 219e1cce3a3SOndrej Mosnacek const struct avtab_key *key) 2201da177e4SLinus Torvalds { 2211da177e4SLinus Torvalds int hvalue; 2221da177e4SLinus Torvalds struct avtab_node *cur; 223782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 2241da177e4SLinus Torvalds 225442dc00fSOndrej Mosnacek if (!h || !h->nslot) 2261da177e4SLinus Torvalds return NULL; 2271da177e4SLinus Torvalds 2283232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 229acdf52d9SKent Overstreet for (cur = h->htable[hvalue]; cur; 230ba39db6eSStephen Smalley cur = cur->next) { 2311da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2321da177e4SLinus Torvalds key->target_type == cur->key.target_type && 2331da177e4SLinus Torvalds key->target_class == cur->key.target_class && 234782ebb99SStephen Smalley (specified & cur->key.specified)) 2351da177e4SLinus Torvalds return cur; 2361da177e4SLinus Torvalds 2371da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 2381da177e4SLinus Torvalds break; 2391da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2401da177e4SLinus Torvalds key->target_type < cur->key.target_type) 2411da177e4SLinus Torvalds break; 2421da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2431da177e4SLinus Torvalds key->target_type == cur->key.target_type && 2441da177e4SLinus Torvalds key->target_class < cur->key.target_class) 2451da177e4SLinus Torvalds break; 2461da177e4SLinus Torvalds } 2471da177e4SLinus Torvalds return NULL; 2481da177e4SLinus Torvalds } 2491da177e4SLinus Torvalds 2501da177e4SLinus Torvalds struct avtab_node* 2511da177e4SLinus Torvalds avtab_search_node_next(struct avtab_node *node, int specified) 2521da177e4SLinus Torvalds { 2531da177e4SLinus Torvalds struct avtab_node *cur; 2541da177e4SLinus Torvalds 2551da177e4SLinus Torvalds if (!node) 2561da177e4SLinus Torvalds return NULL; 2571da177e4SLinus Torvalds 258782ebb99SStephen Smalley specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 2591da177e4SLinus Torvalds for (cur = node->next; cur; cur = cur->next) { 2601da177e4SLinus Torvalds if (node->key.source_type == cur->key.source_type && 2611da177e4SLinus Torvalds node->key.target_type == cur->key.target_type && 2621da177e4SLinus Torvalds node->key.target_class == cur->key.target_class && 263782ebb99SStephen Smalley (specified & cur->key.specified)) 2641da177e4SLinus Torvalds return cur; 2651da177e4SLinus Torvalds 2661da177e4SLinus Torvalds if (node->key.source_type < cur->key.source_type) 2671da177e4SLinus Torvalds break; 2681da177e4SLinus Torvalds if (node->key.source_type == cur->key.source_type && 2691da177e4SLinus Torvalds node->key.target_type < cur->key.target_type) 2701da177e4SLinus Torvalds break; 2711da177e4SLinus Torvalds if (node->key.source_type == cur->key.source_type && 2721da177e4SLinus Torvalds node->key.target_type == cur->key.target_type && 2731da177e4SLinus Torvalds node->key.target_class < cur->key.target_class) 2741da177e4SLinus Torvalds break; 2751da177e4SLinus Torvalds } 2761da177e4SLinus Torvalds return NULL; 2771da177e4SLinus Torvalds } 2781da177e4SLinus Torvalds 2791da177e4SLinus Torvalds void avtab_destroy(struct avtab *h) 2801da177e4SLinus Torvalds { 2811da177e4SLinus Torvalds int i; 2821da177e4SLinus Torvalds struct avtab_node *cur, *temp; 2831da177e4SLinus Torvalds 284acdf52d9SKent Overstreet if (!h) 2851da177e4SLinus Torvalds return; 2861da177e4SLinus Torvalds 2873232c110SYuichi Nakamura for (i = 0; i < h->nslot; i++) { 288acdf52d9SKent Overstreet cur = h->htable[i]; 289dbc74c65SVesa-Matti Kari while (cur) { 2901da177e4SLinus Torvalds temp = cur; 2911da177e4SLinus Torvalds cur = cur->next; 292fa1aa143SJeff Vander Stoep if (temp->key.specified & AVTAB_XPERMS) 293fa1aa143SJeff Vander Stoep kmem_cache_free(avtab_xperms_cachep, 294fa1aa143SJeff Vander Stoep temp->datum.u.xperms); 2951da177e4SLinus Torvalds kmem_cache_free(avtab_node_cachep, temp); 2961da177e4SLinus Torvalds } 2971da177e4SLinus Torvalds } 298acdf52d9SKent Overstreet kvfree(h->htable); 2991da177e4SLinus Torvalds h->htable = NULL; 300442dc00fSOndrej Mosnacek h->nel = 0; 3013232c110SYuichi Nakamura h->nslot = 0; 3023232c110SYuichi Nakamura h->mask = 0; 3031da177e4SLinus Torvalds } 3041da177e4SLinus Torvalds 3055e729e11SPaul Moore void avtab_init(struct avtab *h) 3061da177e4SLinus Torvalds { 3073232c110SYuichi Nakamura h->htable = NULL; 3083232c110SYuichi Nakamura h->nel = 0; 309442dc00fSOndrej Mosnacek h->nslot = 0; 310442dc00fSOndrej Mosnacek h->mask = 0; 3113232c110SYuichi Nakamura } 3121da177e4SLinus Torvalds 313d8f5f0eaSOndrej Mosnacek static int avtab_alloc_common(struct avtab *h, u32 nslot) 3143232c110SYuichi Nakamura { 315d8f5f0eaSOndrej Mosnacek if (!nslot) 316d8f5f0eaSOndrej Mosnacek return 0; 3173232c110SYuichi Nakamura 318acdf52d9SKent Overstreet h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL); 3191da177e4SLinus Torvalds if (!h->htable) 3201da177e4SLinus Torvalds return -ENOMEM; 3213232c110SYuichi Nakamura 3223232c110SYuichi Nakamura h->nslot = nslot; 323442dc00fSOndrej Mosnacek h->mask = nslot - 1; 3241da177e4SLinus Torvalds return 0; 3251da177e4SLinus Torvalds } 3261da177e4SLinus Torvalds 327d8f5f0eaSOndrej Mosnacek int avtab_alloc(struct avtab *h, u32 nrules) 328c7c556f1SStephen Smalley { 329d8f5f0eaSOndrej Mosnacek int rc; 330d8f5f0eaSOndrej Mosnacek u32 nslot = 0; 331c7c556f1SStephen Smalley 332d8f5f0eaSOndrej Mosnacek if (nrules != 0) { 333d8f5f0eaSOndrej Mosnacek u32 shift = 1; 334d8f5f0eaSOndrej Mosnacek u32 work = nrules >> 3; 335d8f5f0eaSOndrej Mosnacek while (work) { 336d8f5f0eaSOndrej Mosnacek work >>= 1; 337d8f5f0eaSOndrej Mosnacek shift++; 338c7c556f1SStephen Smalley } 339d8f5f0eaSOndrej Mosnacek nslot = 1 << shift; 340d8f5f0eaSOndrej Mosnacek if (nslot > MAX_AVTAB_HASH_BUCKETS) 341d8f5f0eaSOndrej Mosnacek nslot = MAX_AVTAB_HASH_BUCKETS; 342c7c556f1SStephen Smalley 343d8f5f0eaSOndrej Mosnacek rc = avtab_alloc_common(h, nslot); 344d8f5f0eaSOndrej Mosnacek if (rc) 345d8f5f0eaSOndrej Mosnacek return rc; 346c7c556f1SStephen Smalley } 347c7c556f1SStephen Smalley 348d8f5f0eaSOndrej Mosnacek pr_debug("SELinux: %d avtab hash slots, %d rules.\n", nslot, nrules); 349c7c556f1SStephen Smalley return 0; 350d8f5f0eaSOndrej Mosnacek } 351d8f5f0eaSOndrej Mosnacek 352d8f5f0eaSOndrej Mosnacek int avtab_alloc_dup(struct avtab *new, const struct avtab *orig) 353d8f5f0eaSOndrej Mosnacek { 354d8f5f0eaSOndrej Mosnacek return avtab_alloc_common(new, orig->nslot); 355c7c556f1SStephen Smalley } 356c7c556f1SStephen Smalley 3571da177e4SLinus Torvalds void avtab_hash_eval(struct avtab *h, char *tag) 3581da177e4SLinus Torvalds { 3591da177e4SLinus Torvalds int i, chain_len, slots_used, max_chain_len; 3603232c110SYuichi Nakamura unsigned long long chain2_len_sum; 3611da177e4SLinus Torvalds struct avtab_node *cur; 3621da177e4SLinus Torvalds 3631da177e4SLinus Torvalds slots_used = 0; 3641da177e4SLinus Torvalds max_chain_len = 0; 3653232c110SYuichi Nakamura chain2_len_sum = 0; 3663232c110SYuichi Nakamura for (i = 0; i < h->nslot; i++) { 367acdf52d9SKent Overstreet cur = h->htable[i]; 3681da177e4SLinus Torvalds if (cur) { 3691da177e4SLinus Torvalds slots_used++; 3701da177e4SLinus Torvalds chain_len = 0; 3711da177e4SLinus Torvalds while (cur) { 3721da177e4SLinus Torvalds chain_len++; 3731da177e4SLinus Torvalds cur = cur->next; 3741da177e4SLinus Torvalds } 3751da177e4SLinus Torvalds 3761da177e4SLinus Torvalds if (chain_len > max_chain_len) 3771da177e4SLinus Torvalds max_chain_len = chain_len; 3783232c110SYuichi Nakamura chain2_len_sum += chain_len * chain_len; 3791da177e4SLinus Torvalds } 3801da177e4SLinus Torvalds } 3811da177e4SLinus Torvalds 382c87a7e75Speter enderborg pr_debug("SELinux: %s: %d entries and %d/%d buckets used, " 383f5269710SEric Paris "longest chain length %d sum of chain length^2 %llu\n", 3843232c110SYuichi Nakamura tag, h->nel, slots_used, h->nslot, max_chain_len, 3853232c110SYuichi Nakamura chain2_len_sum); 3861da177e4SLinus Torvalds } 3871da177e4SLinus Torvalds 388782ebb99SStephen Smalley static uint16_t spec_order[] = { 389782ebb99SStephen Smalley AVTAB_ALLOWED, 390782ebb99SStephen Smalley AVTAB_AUDITDENY, 391782ebb99SStephen Smalley AVTAB_AUDITALLOW, 392782ebb99SStephen Smalley AVTAB_TRANSITION, 393782ebb99SStephen Smalley AVTAB_CHANGE, 394fa1aa143SJeff Vander Stoep AVTAB_MEMBER, 395fa1aa143SJeff Vander Stoep AVTAB_XPERMS_ALLOWED, 396fa1aa143SJeff Vander Stoep AVTAB_XPERMS_AUDITALLOW, 397fa1aa143SJeff Vander Stoep AVTAB_XPERMS_DONTAUDIT 398782ebb99SStephen Smalley }; 399782ebb99SStephen Smalley 40045e5421eSStephen Smalley int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, 401e1cce3a3SOndrej Mosnacek int (*insertf)(struct avtab *a, const struct avtab_key *k, 402e1cce3a3SOndrej Mosnacek const struct avtab_datum *d, void *p), 403782ebb99SStephen Smalley void *p) 4041da177e4SLinus Torvalds { 405b5bf6c55SAlexey Dobriyan __le16 buf16[4]; 406b5bf6c55SAlexey Dobriyan u16 enabled; 40745e5421eSStephen Smalley u32 items, items2, val, vers = pol->policyvers; 408782ebb99SStephen Smalley struct avtab_key key; 409782ebb99SStephen Smalley struct avtab_datum datum; 410fa1aa143SJeff Vander Stoep struct avtab_extended_perms xperms; 411fa1aa143SJeff Vander Stoep __le32 buf32[ARRAY_SIZE(xperms.perms.p)]; 412782ebb99SStephen Smalley int i, rc; 41345e5421eSStephen Smalley unsigned set; 4141da177e4SLinus Torvalds 415782ebb99SStephen Smalley memset(&key, 0, sizeof(struct avtab_key)); 416782ebb99SStephen Smalley memset(&datum, 0, sizeof(struct avtab_datum)); 4171da177e4SLinus Torvalds 418782ebb99SStephen Smalley if (vers < POLICYDB_VERSION_AVTAB) { 419782ebb99SStephen Smalley rc = next_entry(buf32, fp, sizeof(u32)); 4209e0bd4cbSDan Carpenter if (rc) { 421c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 4229e0bd4cbSDan Carpenter return rc; 4231da177e4SLinus Torvalds } 424782ebb99SStephen Smalley items2 = le32_to_cpu(buf32[0]); 425782ebb99SStephen Smalley if (items2 > ARRAY_SIZE(buf32)) { 426c87a7e75Speter enderborg pr_err("SELinux: avtab: entry overflow\n"); 4279e0bd4cbSDan Carpenter return -EINVAL; 428782ebb99SStephen Smalley 4291da177e4SLinus Torvalds } 430782ebb99SStephen Smalley rc = next_entry(buf32, fp, sizeof(u32)*items2); 4319e0bd4cbSDan Carpenter if (rc) { 432c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 4339e0bd4cbSDan Carpenter return rc; 4341da177e4SLinus Torvalds } 4351da177e4SLinus Torvalds items = 0; 4361da177e4SLinus Torvalds 437782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 438782ebb99SStephen Smalley key.source_type = (u16)val; 439782ebb99SStephen Smalley if (key.source_type != val) { 440c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated source type\n"); 4419e0bd4cbSDan Carpenter return -EINVAL; 442782ebb99SStephen Smalley } 443782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 444782ebb99SStephen Smalley key.target_type = (u16)val; 445782ebb99SStephen Smalley if (key.target_type != val) { 446c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated target type\n"); 4479e0bd4cbSDan Carpenter return -EINVAL; 448782ebb99SStephen Smalley } 449782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 450782ebb99SStephen Smalley key.target_class = (u16)val; 451782ebb99SStephen Smalley if (key.target_class != val) { 452c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated target class\n"); 4539e0bd4cbSDan Carpenter return -EINVAL; 4541da177e4SLinus Torvalds } 4551da177e4SLinus Torvalds 456782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 457782ebb99SStephen Smalley enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 458782ebb99SStephen Smalley 459782ebb99SStephen Smalley if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 460c87a7e75Speter enderborg pr_err("SELinux: avtab: null entry\n"); 4619e0bd4cbSDan Carpenter return -EINVAL; 462782ebb99SStephen Smalley } 463782ebb99SStephen Smalley if ((val & AVTAB_AV) && 464782ebb99SStephen Smalley (val & AVTAB_TYPE)) { 465c87a7e75Speter enderborg pr_err("SELinux: avtab: entry has both access vectors and types\n"); 4669e0bd4cbSDan Carpenter return -EINVAL; 467782ebb99SStephen Smalley } 468fa1aa143SJeff Vander Stoep if (val & AVTAB_XPERMS) { 469c87a7e75Speter enderborg pr_err("SELinux: avtab: entry has extended permissions\n"); 470fa1aa143SJeff Vander Stoep return -EINVAL; 471fa1aa143SJeff Vander Stoep } 472782ebb99SStephen Smalley 47332725ad8STobias Klauser for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 474782ebb99SStephen Smalley if (val & spec_order[i]) { 475782ebb99SStephen Smalley key.specified = spec_order[i] | enabled; 476fa1aa143SJeff Vander Stoep datum.u.data = le32_to_cpu(buf32[items++]); 477782ebb99SStephen Smalley rc = insertf(a, &key, &datum, p); 478eb5df9a7SEric Paris if (rc) 479eb5df9a7SEric Paris return rc; 480782ebb99SStephen Smalley } 481782ebb99SStephen Smalley } 482782ebb99SStephen Smalley 483782ebb99SStephen Smalley if (items != items2) { 484c87a7e75Speter enderborg pr_err("SELinux: avtab: entry only had %d items, expected %d\n", 485c87a7e75Speter enderborg items2, items); 4869e0bd4cbSDan Carpenter return -EINVAL; 487782ebb99SStephen Smalley } 488782ebb99SStephen Smalley return 0; 489782ebb99SStephen Smalley } 490782ebb99SStephen Smalley 491782ebb99SStephen Smalley rc = next_entry(buf16, fp, sizeof(u16)*4); 4929e0bd4cbSDan Carpenter if (rc) { 493c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 4949e0bd4cbSDan Carpenter return rc; 495782ebb99SStephen Smalley } 496782ebb99SStephen Smalley 497782ebb99SStephen Smalley items = 0; 498782ebb99SStephen Smalley key.source_type = le16_to_cpu(buf16[items++]); 499782ebb99SStephen Smalley key.target_type = le16_to_cpu(buf16[items++]); 500782ebb99SStephen Smalley key.target_class = le16_to_cpu(buf16[items++]); 501782ebb99SStephen Smalley key.specified = le16_to_cpu(buf16[items++]); 502782ebb99SStephen Smalley 50345e5421eSStephen Smalley if (!policydb_type_isvalid(pol, key.source_type) || 50445e5421eSStephen Smalley !policydb_type_isvalid(pol, key.target_type) || 50545e5421eSStephen Smalley !policydb_class_isvalid(pol, key.target_class)) { 506c87a7e75Speter enderborg pr_err("SELinux: avtab: invalid type or class\n"); 5079e0bd4cbSDan Carpenter return -EINVAL; 50845e5421eSStephen Smalley } 50945e5421eSStephen Smalley 51045e5421eSStephen Smalley set = 0; 51145e5421eSStephen Smalley for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 51245e5421eSStephen Smalley if (key.specified & spec_order[i]) 51345e5421eSStephen Smalley set++; 51445e5421eSStephen Smalley } 51545e5421eSStephen Smalley if (!set || set > 1) { 516c87a7e75Speter enderborg pr_err("SELinux: avtab: more than one specifier\n"); 5179e0bd4cbSDan Carpenter return -EINVAL; 51845e5421eSStephen Smalley } 51945e5421eSStephen Smalley 520fa1aa143SJeff Vander Stoep if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) && 521fa1aa143SJeff Vander Stoep (key.specified & AVTAB_XPERMS)) { 522c87a7e75Speter enderborg pr_err("SELinux: avtab: policy version %u does not " 523fa1aa143SJeff Vander Stoep "support extended permissions rules and one " 524fa1aa143SJeff Vander Stoep "was specified\n", vers); 525fa1aa143SJeff Vander Stoep return -EINVAL; 526fa1aa143SJeff Vander Stoep } else if (key.specified & AVTAB_XPERMS) { 527fa1aa143SJeff Vander Stoep memset(&xperms, 0, sizeof(struct avtab_extended_perms)); 528fa1aa143SJeff Vander Stoep rc = next_entry(&xperms.specified, fp, sizeof(u8)); 529fa1aa143SJeff Vander Stoep if (rc) { 530c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 531fa1aa143SJeff Vander Stoep return rc; 532fa1aa143SJeff Vander Stoep } 533fa1aa143SJeff Vander Stoep rc = next_entry(&xperms.driver, fp, sizeof(u8)); 534fa1aa143SJeff Vander Stoep if (rc) { 535c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 536fa1aa143SJeff Vander Stoep return rc; 537fa1aa143SJeff Vander Stoep } 538fa1aa143SJeff Vander Stoep rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p)); 539fa1aa143SJeff Vander Stoep if (rc) { 540c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 541fa1aa143SJeff Vander Stoep return rc; 542fa1aa143SJeff Vander Stoep } 543fa1aa143SJeff Vander Stoep for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++) 544fa1aa143SJeff Vander Stoep xperms.perms.p[i] = le32_to_cpu(buf32[i]); 545fa1aa143SJeff Vander Stoep datum.u.xperms = &xperms; 546fa1aa143SJeff Vander Stoep } else { 547782ebb99SStephen Smalley rc = next_entry(buf32, fp, sizeof(u32)); 5489e0bd4cbSDan Carpenter if (rc) { 549c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 5509e0bd4cbSDan Carpenter return rc; 551782ebb99SStephen Smalley } 552fa1aa143SJeff Vander Stoep datum.u.data = le32_to_cpu(*buf32); 553fa1aa143SJeff Vander Stoep } 55445e5421eSStephen Smalley if ((key.specified & AVTAB_TYPE) && 555fa1aa143SJeff Vander Stoep !policydb_type_isvalid(pol, datum.u.data)) { 556c87a7e75Speter enderborg pr_err("SELinux: avtab: invalid type\n"); 5579e0bd4cbSDan Carpenter return -EINVAL; 55845e5421eSStephen Smalley } 559782ebb99SStephen Smalley return insertf(a, &key, &datum, p); 560782ebb99SStephen Smalley } 561782ebb99SStephen Smalley 562e1cce3a3SOndrej Mosnacek static int avtab_insertf(struct avtab *a, const struct avtab_key *k, 563e1cce3a3SOndrej Mosnacek const struct avtab_datum *d, void *p) 564782ebb99SStephen Smalley { 565782ebb99SStephen Smalley return avtab_insert(a, k, d); 566782ebb99SStephen Smalley } 567782ebb99SStephen Smalley 56845e5421eSStephen Smalley int avtab_read(struct avtab *a, void *fp, struct policydb *pol) 5691da177e4SLinus Torvalds { 5701da177e4SLinus Torvalds int rc; 571b5bf6c55SAlexey Dobriyan __le32 buf[1]; 5721da177e4SLinus Torvalds u32 nel, i; 5731da177e4SLinus Torvalds 5741da177e4SLinus Torvalds 5751da177e4SLinus Torvalds rc = next_entry(buf, fp, sizeof(u32)); 5761da177e4SLinus Torvalds if (rc < 0) { 577c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated table\n"); 5781da177e4SLinus Torvalds goto bad; 5791da177e4SLinus Torvalds } 5801da177e4SLinus Torvalds nel = le32_to_cpu(buf[0]); 5811da177e4SLinus Torvalds if (!nel) { 582c87a7e75Speter enderborg pr_err("SELinux: avtab: table is empty\n"); 5831da177e4SLinus Torvalds rc = -EINVAL; 5841da177e4SLinus Torvalds goto bad; 5851da177e4SLinus Torvalds } 5863232c110SYuichi Nakamura 5873232c110SYuichi Nakamura rc = avtab_alloc(a, nel); 5883232c110SYuichi Nakamura if (rc) 5893232c110SYuichi Nakamura goto bad; 5903232c110SYuichi Nakamura 5911da177e4SLinus Torvalds for (i = 0; i < nel; i++) { 59245e5421eSStephen Smalley rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); 5931da177e4SLinus Torvalds if (rc) { 5941da177e4SLinus Torvalds if (rc == -ENOMEM) 595c87a7e75Speter enderborg pr_err("SELinux: avtab: out of memory\n"); 596782ebb99SStephen Smalley else if (rc == -EEXIST) 597c87a7e75Speter enderborg pr_err("SELinux: avtab: duplicate entry\n"); 5989e0bd4cbSDan Carpenter 5991da177e4SLinus Torvalds goto bad; 6001da177e4SLinus Torvalds } 6011da177e4SLinus Torvalds } 6021da177e4SLinus Torvalds 6031da177e4SLinus Torvalds rc = 0; 6041da177e4SLinus Torvalds out: 6051da177e4SLinus Torvalds return rc; 6061da177e4SLinus Torvalds 6071da177e4SLinus Torvalds bad: 6081da177e4SLinus Torvalds avtab_destroy(a); 6091da177e4SLinus Torvalds goto out; 6101da177e4SLinus Torvalds } 6111da177e4SLinus Torvalds 612e1cce3a3SOndrej Mosnacek int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp) 613cee74f47SEric Paris { 614cee74f47SEric Paris __le16 buf16[4]; 615fa1aa143SJeff Vander Stoep __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)]; 616cee74f47SEric Paris int rc; 617fa1aa143SJeff Vander Stoep unsigned int i; 618cee74f47SEric Paris 619cee74f47SEric Paris buf16[0] = cpu_to_le16(cur->key.source_type); 620cee74f47SEric Paris buf16[1] = cpu_to_le16(cur->key.target_type); 621cee74f47SEric Paris buf16[2] = cpu_to_le16(cur->key.target_class); 622cee74f47SEric Paris buf16[3] = cpu_to_le16(cur->key.specified); 623cee74f47SEric Paris rc = put_entry(buf16, sizeof(u16), 4, fp); 624cee74f47SEric Paris if (rc) 625cee74f47SEric Paris return rc; 626fa1aa143SJeff Vander Stoep 627fa1aa143SJeff Vander Stoep if (cur->key.specified & AVTAB_XPERMS) { 628fa1aa143SJeff Vander Stoep rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp); 629fa1aa143SJeff Vander Stoep if (rc) 630fa1aa143SJeff Vander Stoep return rc; 631fa1aa143SJeff Vander Stoep rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp); 632fa1aa143SJeff Vander Stoep if (rc) 633fa1aa143SJeff Vander Stoep return rc; 634fa1aa143SJeff Vander Stoep for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++) 635fa1aa143SJeff Vander Stoep buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]); 636fa1aa143SJeff Vander Stoep rc = put_entry(buf32, sizeof(u32), 637fa1aa143SJeff Vander Stoep ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp); 638fa1aa143SJeff Vander Stoep } else { 639fa1aa143SJeff Vander Stoep buf32[0] = cpu_to_le32(cur->datum.u.data); 640cee74f47SEric Paris rc = put_entry(buf32, sizeof(u32), 1, fp); 641fa1aa143SJeff Vander Stoep } 642cee74f47SEric Paris if (rc) 643cee74f47SEric Paris return rc; 644cee74f47SEric Paris return 0; 645cee74f47SEric Paris } 646cee74f47SEric Paris 647cee74f47SEric Paris int avtab_write(struct policydb *p, struct avtab *a, void *fp) 648cee74f47SEric Paris { 649cee74f47SEric Paris unsigned int i; 650cee74f47SEric Paris int rc = 0; 651cee74f47SEric Paris struct avtab_node *cur; 652cee74f47SEric Paris __le32 buf[1]; 653cee74f47SEric Paris 654cee74f47SEric Paris buf[0] = cpu_to_le32(a->nel); 655cee74f47SEric Paris rc = put_entry(buf, sizeof(u32), 1, fp); 656cee74f47SEric Paris if (rc) 657cee74f47SEric Paris return rc; 658cee74f47SEric Paris 659cee74f47SEric Paris for (i = 0; i < a->nslot; i++) { 660acdf52d9SKent Overstreet for (cur = a->htable[i]; cur; 661ba39db6eSStephen Smalley cur = cur->next) { 662cee74f47SEric Paris rc = avtab_write_item(p, cur, fp); 663cee74f47SEric Paris if (rc) 664cee74f47SEric Paris return rc; 665cee74f47SEric Paris } 666cee74f47SEric Paris } 667cee74f47SEric Paris 668cee74f47SEric Paris return rc; 669cee74f47SEric Paris } 670aa8e712cSStephen Smalley 671aa8e712cSStephen Smalley void __init avtab_cache_init(void) 6721da177e4SLinus Torvalds { 6731da177e4SLinus Torvalds avtab_node_cachep = kmem_cache_create("avtab_node", 6741da177e4SLinus Torvalds sizeof(struct avtab_node), 67520c2df83SPaul Mundt 0, SLAB_PANIC, NULL); 676fa1aa143SJeff Vander Stoep avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms", 677fa1aa143SJeff Vander Stoep sizeof(struct avtab_extended_perms), 678fa1aa143SJeff Vander Stoep 0, SLAB_PANIC, NULL); 6791da177e4SLinus Torvalds } 680