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 26e18b890bSChristoph Lameter static struct kmem_cache *avtab_node_cachep; 27fa1aa143SJeff Vander Stoep static struct kmem_cache *avtab_xperms_cachep; 281da177e4SLinus Torvalds 2933ebc193SJohn Brooks /* Based on MurmurHash3, written by Austin Appleby and placed in the 3033ebc193SJohn Brooks * public domain. 3133ebc193SJohn Brooks */ 3233ebc193SJohn Brooks static inline int avtab_hash(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, 701da177e4SLinus Torvalds struct avtab_node *prev, struct avtab_node *cur, 711da177e4SLinus Torvalds struct avtab_key *key, 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 1061da177e4SLinus Torvalds static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum) 1071da177e4SLinus Torvalds { 1081da177e4SLinus Torvalds int hvalue; 1091da177e4SLinus Torvalds struct avtab_node *prev, *cur, *newnode; 110782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 1111da177e4SLinus Torvalds 112acdf52d9SKent Overstreet if (!h) 1131da177e4SLinus Torvalds return -EINVAL; 1141da177e4SLinus Torvalds 1153232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 116acdf52d9SKent Overstreet for (prev = NULL, cur = h->htable[hvalue]; 1171da177e4SLinus Torvalds cur; 1181da177e4SLinus Torvalds prev = cur, cur = cur->next) { 1191da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1201da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1211da177e4SLinus Torvalds key->target_class == cur->key.target_class && 122fa1aa143SJeff Vander Stoep (specified & cur->key.specified)) { 123fa1aa143SJeff Vander Stoep /* extended perms may not be unique */ 124fa1aa143SJeff Vander Stoep if (specified & AVTAB_XPERMS) 125fa1aa143SJeff Vander Stoep break; 1261da177e4SLinus Torvalds return -EEXIST; 127fa1aa143SJeff Vander Stoep } 1281da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 1291da177e4SLinus Torvalds break; 1301da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1311da177e4SLinus Torvalds key->target_type < cur->key.target_type) 1321da177e4SLinus Torvalds break; 1331da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1341da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1351da177e4SLinus Torvalds key->target_class < cur->key.target_class) 1361da177e4SLinus Torvalds break; 1371da177e4SLinus Torvalds } 1381da177e4SLinus Torvalds 1391da177e4SLinus Torvalds newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum); 1401da177e4SLinus Torvalds if (!newnode) 1411da177e4SLinus Torvalds return -ENOMEM; 1421da177e4SLinus Torvalds 1431da177e4SLinus Torvalds return 0; 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds 1461da177e4SLinus Torvalds /* Unlike avtab_insert(), this function allow multiple insertions of the same 1471da177e4SLinus Torvalds * key/specified mask into the table, as needed by the conditional avtab. 1481da177e4SLinus Torvalds * It also returns a pointer to the node inserted. 1491da177e4SLinus Torvalds */ 1501da177e4SLinus Torvalds struct avtab_node * 1511da177e4SLinus Torvalds avtab_insert_nonunique(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum) 1521da177e4SLinus Torvalds { 1531da177e4SLinus Torvalds int hvalue; 1540c0e186fSVesa-Matti J Kari struct avtab_node *prev, *cur; 155782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 1561da177e4SLinus Torvalds 157acdf52d9SKent Overstreet if (!h) 1581da177e4SLinus Torvalds return NULL; 1593232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 160acdf52d9SKent Overstreet for (prev = NULL, cur = h->htable[hvalue]; 1611da177e4SLinus Torvalds cur; 1621da177e4SLinus Torvalds prev = cur, cur = cur->next) { 1631da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1641da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1651da177e4SLinus Torvalds key->target_class == cur->key.target_class && 166782ebb99SStephen Smalley (specified & cur->key.specified)) 1671da177e4SLinus Torvalds break; 1681da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 1691da177e4SLinus Torvalds break; 1701da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1711da177e4SLinus Torvalds key->target_type < cur->key.target_type) 1721da177e4SLinus Torvalds break; 1731da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1741da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1751da177e4SLinus Torvalds key->target_class < cur->key.target_class) 1761da177e4SLinus Torvalds break; 1771da177e4SLinus Torvalds } 1780c0e186fSVesa-Matti J Kari return avtab_insert_node(h, hvalue, prev, cur, key, datum); 1791da177e4SLinus Torvalds } 1801da177e4SLinus Torvalds 181782ebb99SStephen Smalley struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key) 1821da177e4SLinus Torvalds { 1831da177e4SLinus Torvalds int hvalue; 1841da177e4SLinus Torvalds struct avtab_node *cur; 185782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 1861da177e4SLinus Torvalds 187acdf52d9SKent Overstreet if (!h) 1881da177e4SLinus Torvalds return NULL; 1891da177e4SLinus Torvalds 1903232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 191acdf52d9SKent Overstreet for (cur = h->htable[hvalue]; cur; 192ba39db6eSStephen Smalley cur = cur->next) { 1931da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 1941da177e4SLinus Torvalds key->target_type == cur->key.target_type && 1951da177e4SLinus Torvalds key->target_class == cur->key.target_class && 196782ebb99SStephen Smalley (specified & cur->key.specified)) 1971da177e4SLinus Torvalds return &cur->datum; 1981da177e4SLinus Torvalds 1991da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 2001da177e4SLinus Torvalds break; 2011da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2021da177e4SLinus Torvalds key->target_type < cur->key.target_type) 2031da177e4SLinus Torvalds break; 2041da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2051da177e4SLinus Torvalds key->target_type == cur->key.target_type && 2061da177e4SLinus Torvalds key->target_class < cur->key.target_class) 2071da177e4SLinus Torvalds break; 2081da177e4SLinus Torvalds } 2091da177e4SLinus Torvalds 2101da177e4SLinus Torvalds return NULL; 2111da177e4SLinus Torvalds } 2121da177e4SLinus Torvalds 2131da177e4SLinus Torvalds /* This search function returns a node pointer, and can be used in 2141da177e4SLinus Torvalds * conjunction with avtab_search_next_node() 2151da177e4SLinus Torvalds */ 2161da177e4SLinus Torvalds struct avtab_node* 217782ebb99SStephen Smalley avtab_search_node(struct avtab *h, struct avtab_key *key) 2181da177e4SLinus Torvalds { 2191da177e4SLinus Torvalds int hvalue; 2201da177e4SLinus Torvalds struct avtab_node *cur; 221782ebb99SStephen Smalley u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 2221da177e4SLinus Torvalds 223acdf52d9SKent Overstreet if (!h) 2241da177e4SLinus Torvalds return NULL; 2251da177e4SLinus Torvalds 2263232c110SYuichi Nakamura hvalue = avtab_hash(key, h->mask); 227acdf52d9SKent Overstreet for (cur = h->htable[hvalue]; cur; 228ba39db6eSStephen Smalley cur = cur->next) { 2291da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2301da177e4SLinus Torvalds key->target_type == cur->key.target_type && 2311da177e4SLinus Torvalds key->target_class == cur->key.target_class && 232782ebb99SStephen Smalley (specified & cur->key.specified)) 2331da177e4SLinus Torvalds return cur; 2341da177e4SLinus Torvalds 2351da177e4SLinus Torvalds if (key->source_type < cur->key.source_type) 2361da177e4SLinus Torvalds break; 2371da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2381da177e4SLinus Torvalds key->target_type < cur->key.target_type) 2391da177e4SLinus Torvalds break; 2401da177e4SLinus Torvalds if (key->source_type == cur->key.source_type && 2411da177e4SLinus Torvalds key->target_type == cur->key.target_type && 2421da177e4SLinus Torvalds key->target_class < cur->key.target_class) 2431da177e4SLinus Torvalds break; 2441da177e4SLinus Torvalds } 2451da177e4SLinus Torvalds return NULL; 2461da177e4SLinus Torvalds } 2471da177e4SLinus Torvalds 2481da177e4SLinus Torvalds struct avtab_node* 2491da177e4SLinus Torvalds avtab_search_node_next(struct avtab_node *node, int specified) 2501da177e4SLinus Torvalds { 2511da177e4SLinus Torvalds struct avtab_node *cur; 2521da177e4SLinus Torvalds 2531da177e4SLinus Torvalds if (!node) 2541da177e4SLinus Torvalds return NULL; 2551da177e4SLinus Torvalds 256782ebb99SStephen Smalley specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD); 2571da177e4SLinus Torvalds for (cur = node->next; cur; cur = cur->next) { 2581da177e4SLinus Torvalds if (node->key.source_type == cur->key.source_type && 2591da177e4SLinus Torvalds node->key.target_type == cur->key.target_type && 2601da177e4SLinus Torvalds node->key.target_class == cur->key.target_class && 261782ebb99SStephen Smalley (specified & cur->key.specified)) 2621da177e4SLinus Torvalds return cur; 2631da177e4SLinus Torvalds 2641da177e4SLinus Torvalds if (node->key.source_type < cur->key.source_type) 2651da177e4SLinus Torvalds break; 2661da177e4SLinus Torvalds if (node->key.source_type == cur->key.source_type && 2671da177e4SLinus Torvalds node->key.target_type < cur->key.target_type) 2681da177e4SLinus Torvalds break; 2691da177e4SLinus Torvalds if (node->key.source_type == cur->key.source_type && 2701da177e4SLinus Torvalds node->key.target_type == cur->key.target_type && 2711da177e4SLinus Torvalds node->key.target_class < cur->key.target_class) 2721da177e4SLinus Torvalds break; 2731da177e4SLinus Torvalds } 2741da177e4SLinus Torvalds return NULL; 2751da177e4SLinus Torvalds } 2761da177e4SLinus Torvalds 2771da177e4SLinus Torvalds void avtab_destroy(struct avtab *h) 2781da177e4SLinus Torvalds { 2791da177e4SLinus Torvalds int i; 2801da177e4SLinus Torvalds struct avtab_node *cur, *temp; 2811da177e4SLinus Torvalds 282acdf52d9SKent Overstreet if (!h) 2831da177e4SLinus Torvalds return; 2841da177e4SLinus Torvalds 2853232c110SYuichi Nakamura for (i = 0; i < h->nslot; i++) { 286acdf52d9SKent Overstreet cur = h->htable[i]; 287dbc74c65SVesa-Matti Kari while (cur) { 2881da177e4SLinus Torvalds temp = cur; 2891da177e4SLinus Torvalds cur = cur->next; 290fa1aa143SJeff Vander Stoep if (temp->key.specified & AVTAB_XPERMS) 291fa1aa143SJeff Vander Stoep kmem_cache_free(avtab_xperms_cachep, 292fa1aa143SJeff Vander Stoep temp->datum.u.xperms); 2931da177e4SLinus Torvalds kmem_cache_free(avtab_node_cachep, temp); 2941da177e4SLinus Torvalds } 2951da177e4SLinus Torvalds } 296acdf52d9SKent Overstreet kvfree(h->htable); 2971da177e4SLinus Torvalds h->htable = NULL; 2983232c110SYuichi Nakamura h->nslot = 0; 2993232c110SYuichi Nakamura h->mask = 0; 3001da177e4SLinus Torvalds } 3011da177e4SLinus Torvalds 3025e729e11SPaul Moore void avtab_init(struct avtab *h) 3031da177e4SLinus Torvalds { 3043232c110SYuichi Nakamura h->htable = NULL; 3053232c110SYuichi Nakamura h->nel = 0; 3063232c110SYuichi Nakamura } 3071da177e4SLinus Torvalds 3083232c110SYuichi Nakamura int avtab_alloc(struct avtab *h, u32 nrules) 3093232c110SYuichi Nakamura { 31033ebc193SJohn Brooks u32 mask = 0; 3113232c110SYuichi Nakamura u32 shift = 0; 3123232c110SYuichi Nakamura u32 work = nrules; 3133232c110SYuichi Nakamura u32 nslot = 0; 3143232c110SYuichi Nakamura 3153232c110SYuichi Nakamura if (nrules == 0) 3163232c110SYuichi Nakamura goto avtab_alloc_out; 3173232c110SYuichi Nakamura 3183232c110SYuichi Nakamura while (work) { 3193232c110SYuichi Nakamura work = work >> 1; 3203232c110SYuichi Nakamura shift++; 3213232c110SYuichi Nakamura } 3223232c110SYuichi Nakamura if (shift > 2) 3233232c110SYuichi Nakamura shift = shift - 2; 3243232c110SYuichi Nakamura nslot = 1 << shift; 32500d85c83SEric Paris if (nslot > MAX_AVTAB_HASH_BUCKETS) 32600d85c83SEric Paris nslot = MAX_AVTAB_HASH_BUCKETS; 3273232c110SYuichi Nakamura mask = nslot - 1; 3283232c110SYuichi Nakamura 329acdf52d9SKent Overstreet h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL); 3301da177e4SLinus Torvalds if (!h->htable) 3311da177e4SLinus Torvalds return -ENOMEM; 3323232c110SYuichi Nakamura 3333232c110SYuichi Nakamura avtab_alloc_out: 3341da177e4SLinus Torvalds h->nel = 0; 3353232c110SYuichi Nakamura h->nslot = nslot; 3363232c110SYuichi Nakamura h->mask = mask; 337c87a7e75Speter enderborg pr_debug("SELinux: %d avtab hash slots, %d rules.\n", 338454d972cSJames Morris h->nslot, nrules); 3391da177e4SLinus Torvalds return 0; 3401da177e4SLinus Torvalds } 3411da177e4SLinus Torvalds 342c7c556f1SStephen Smalley int avtab_duplicate(struct avtab *new, struct avtab *orig) 343c7c556f1SStephen Smalley { 344c7c556f1SStephen Smalley int i; 345c7c556f1SStephen Smalley struct avtab_node *node, *tmp, *tail; 346c7c556f1SStephen Smalley 347c7c556f1SStephen Smalley memset(new, 0, sizeof(*new)); 348c7c556f1SStephen Smalley 349c7c556f1SStephen Smalley new->htable = kvcalloc(orig->nslot, sizeof(void *), GFP_KERNEL); 350c7c556f1SStephen Smalley if (!new->htable) 351c7c556f1SStephen Smalley return -ENOMEM; 352c7c556f1SStephen Smalley new->nslot = orig->nslot; 353c7c556f1SStephen Smalley new->mask = orig->mask; 354c7c556f1SStephen Smalley 355c7c556f1SStephen Smalley for (i = 0; i < orig->nslot; i++) { 356c7c556f1SStephen Smalley tail = NULL; 357c7c556f1SStephen Smalley for (node = orig->htable[i]; node; node = node->next) { 358c7c556f1SStephen Smalley tmp = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); 359c7c556f1SStephen Smalley if (!tmp) 360c7c556f1SStephen Smalley goto error; 361c7c556f1SStephen Smalley tmp->key = node->key; 362c7c556f1SStephen Smalley if (tmp->key.specified & AVTAB_XPERMS) { 363c7c556f1SStephen Smalley tmp->datum.u.xperms = 364c7c556f1SStephen Smalley kmem_cache_zalloc(avtab_xperms_cachep, 365c7c556f1SStephen Smalley GFP_KERNEL); 366c7c556f1SStephen Smalley if (!tmp->datum.u.xperms) { 367c7c556f1SStephen Smalley kmem_cache_free(avtab_node_cachep, tmp); 368c7c556f1SStephen Smalley goto error; 369c7c556f1SStephen Smalley } 370c7c556f1SStephen Smalley tmp->datum.u.xperms = node->datum.u.xperms; 371c7c556f1SStephen Smalley } else 372c7c556f1SStephen Smalley tmp->datum.u.data = node->datum.u.data; 373c7c556f1SStephen Smalley 374c7c556f1SStephen Smalley if (tail) 375c7c556f1SStephen Smalley tail->next = tmp; 376c7c556f1SStephen Smalley else 377c7c556f1SStephen Smalley new->htable[i] = tmp; 378c7c556f1SStephen Smalley 379c7c556f1SStephen Smalley tail = tmp; 380c7c556f1SStephen Smalley new->nel++; 381c7c556f1SStephen Smalley } 382c7c556f1SStephen Smalley } 383c7c556f1SStephen Smalley 384c7c556f1SStephen Smalley return 0; 385c7c556f1SStephen Smalley error: 386c7c556f1SStephen Smalley avtab_destroy(new); 387c7c556f1SStephen Smalley return -ENOMEM; 388c7c556f1SStephen Smalley } 389c7c556f1SStephen Smalley 3901da177e4SLinus Torvalds void avtab_hash_eval(struct avtab *h, char *tag) 3911da177e4SLinus Torvalds { 3921da177e4SLinus Torvalds int i, chain_len, slots_used, max_chain_len; 3933232c110SYuichi Nakamura unsigned long long chain2_len_sum; 3941da177e4SLinus Torvalds struct avtab_node *cur; 3951da177e4SLinus Torvalds 3961da177e4SLinus Torvalds slots_used = 0; 3971da177e4SLinus Torvalds max_chain_len = 0; 3983232c110SYuichi Nakamura chain2_len_sum = 0; 3993232c110SYuichi Nakamura for (i = 0; i < h->nslot; i++) { 400acdf52d9SKent Overstreet cur = h->htable[i]; 4011da177e4SLinus Torvalds if (cur) { 4021da177e4SLinus Torvalds slots_used++; 4031da177e4SLinus Torvalds chain_len = 0; 4041da177e4SLinus Torvalds while (cur) { 4051da177e4SLinus Torvalds chain_len++; 4061da177e4SLinus Torvalds cur = cur->next; 4071da177e4SLinus Torvalds } 4081da177e4SLinus Torvalds 4091da177e4SLinus Torvalds if (chain_len > max_chain_len) 4101da177e4SLinus Torvalds max_chain_len = chain_len; 4113232c110SYuichi Nakamura chain2_len_sum += chain_len * chain_len; 4121da177e4SLinus Torvalds } 4131da177e4SLinus Torvalds } 4141da177e4SLinus Torvalds 415c87a7e75Speter enderborg pr_debug("SELinux: %s: %d entries and %d/%d buckets used, " 416f5269710SEric Paris "longest chain length %d sum of chain length^2 %llu\n", 4173232c110SYuichi Nakamura tag, h->nel, slots_used, h->nslot, max_chain_len, 4183232c110SYuichi Nakamura chain2_len_sum); 4191da177e4SLinus Torvalds } 4201da177e4SLinus Torvalds 421782ebb99SStephen Smalley static uint16_t spec_order[] = { 422782ebb99SStephen Smalley AVTAB_ALLOWED, 423782ebb99SStephen Smalley AVTAB_AUDITDENY, 424782ebb99SStephen Smalley AVTAB_AUDITALLOW, 425782ebb99SStephen Smalley AVTAB_TRANSITION, 426782ebb99SStephen Smalley AVTAB_CHANGE, 427fa1aa143SJeff Vander Stoep AVTAB_MEMBER, 428fa1aa143SJeff Vander Stoep AVTAB_XPERMS_ALLOWED, 429fa1aa143SJeff Vander Stoep AVTAB_XPERMS_AUDITALLOW, 430fa1aa143SJeff Vander Stoep AVTAB_XPERMS_DONTAUDIT 431782ebb99SStephen Smalley }; 432782ebb99SStephen Smalley 43345e5421eSStephen Smalley int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, 434782ebb99SStephen Smalley int (*insertf)(struct avtab *a, struct avtab_key *k, 435782ebb99SStephen Smalley struct avtab_datum *d, void *p), 436782ebb99SStephen Smalley void *p) 4371da177e4SLinus Torvalds { 438b5bf6c55SAlexey Dobriyan __le16 buf16[4]; 439b5bf6c55SAlexey Dobriyan u16 enabled; 44045e5421eSStephen Smalley u32 items, items2, val, vers = pol->policyvers; 441782ebb99SStephen Smalley struct avtab_key key; 442782ebb99SStephen Smalley struct avtab_datum datum; 443fa1aa143SJeff Vander Stoep struct avtab_extended_perms xperms; 444fa1aa143SJeff Vander Stoep __le32 buf32[ARRAY_SIZE(xperms.perms.p)]; 445782ebb99SStephen Smalley int i, rc; 44645e5421eSStephen Smalley unsigned set; 4471da177e4SLinus Torvalds 448782ebb99SStephen Smalley memset(&key, 0, sizeof(struct avtab_key)); 449782ebb99SStephen Smalley memset(&datum, 0, sizeof(struct avtab_datum)); 4501da177e4SLinus Torvalds 451782ebb99SStephen Smalley if (vers < POLICYDB_VERSION_AVTAB) { 452782ebb99SStephen Smalley rc = next_entry(buf32, fp, sizeof(u32)); 4539e0bd4cbSDan Carpenter if (rc) { 454c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 4559e0bd4cbSDan Carpenter return rc; 4561da177e4SLinus Torvalds } 457782ebb99SStephen Smalley items2 = le32_to_cpu(buf32[0]); 458782ebb99SStephen Smalley if (items2 > ARRAY_SIZE(buf32)) { 459c87a7e75Speter enderborg pr_err("SELinux: avtab: entry overflow\n"); 4609e0bd4cbSDan Carpenter return -EINVAL; 461782ebb99SStephen Smalley 4621da177e4SLinus Torvalds } 463782ebb99SStephen Smalley rc = next_entry(buf32, fp, sizeof(u32)*items2); 4649e0bd4cbSDan Carpenter if (rc) { 465c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 4669e0bd4cbSDan Carpenter return rc; 4671da177e4SLinus Torvalds } 4681da177e4SLinus Torvalds items = 0; 4691da177e4SLinus Torvalds 470782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 471782ebb99SStephen Smalley key.source_type = (u16)val; 472782ebb99SStephen Smalley if (key.source_type != val) { 473c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated source type\n"); 4749e0bd4cbSDan Carpenter return -EINVAL; 475782ebb99SStephen Smalley } 476782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 477782ebb99SStephen Smalley key.target_type = (u16)val; 478782ebb99SStephen Smalley if (key.target_type != val) { 479c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated target type\n"); 4809e0bd4cbSDan Carpenter return -EINVAL; 481782ebb99SStephen Smalley } 482782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 483782ebb99SStephen Smalley key.target_class = (u16)val; 484782ebb99SStephen Smalley if (key.target_class != val) { 485c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated target class\n"); 4869e0bd4cbSDan Carpenter return -EINVAL; 4871da177e4SLinus Torvalds } 4881da177e4SLinus Torvalds 489782ebb99SStephen Smalley val = le32_to_cpu(buf32[items++]); 490782ebb99SStephen Smalley enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0; 491782ebb99SStephen Smalley 492782ebb99SStephen Smalley if (!(val & (AVTAB_AV | AVTAB_TYPE))) { 493c87a7e75Speter enderborg pr_err("SELinux: avtab: null entry\n"); 4949e0bd4cbSDan Carpenter return -EINVAL; 495782ebb99SStephen Smalley } 496782ebb99SStephen Smalley if ((val & AVTAB_AV) && 497782ebb99SStephen Smalley (val & AVTAB_TYPE)) { 498c87a7e75Speter enderborg pr_err("SELinux: avtab: entry has both access vectors and types\n"); 4999e0bd4cbSDan Carpenter return -EINVAL; 500782ebb99SStephen Smalley } 501fa1aa143SJeff Vander Stoep if (val & AVTAB_XPERMS) { 502c87a7e75Speter enderborg pr_err("SELinux: avtab: entry has extended permissions\n"); 503fa1aa143SJeff Vander Stoep return -EINVAL; 504fa1aa143SJeff Vander Stoep } 505782ebb99SStephen Smalley 50632725ad8STobias Klauser for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 507782ebb99SStephen Smalley if (val & spec_order[i]) { 508782ebb99SStephen Smalley key.specified = spec_order[i] | enabled; 509fa1aa143SJeff Vander Stoep datum.u.data = le32_to_cpu(buf32[items++]); 510782ebb99SStephen Smalley rc = insertf(a, &key, &datum, p); 511eb5df9a7SEric Paris if (rc) 512eb5df9a7SEric Paris return rc; 513782ebb99SStephen Smalley } 514782ebb99SStephen Smalley } 515782ebb99SStephen Smalley 516782ebb99SStephen Smalley if (items != items2) { 517c87a7e75Speter enderborg pr_err("SELinux: avtab: entry only had %d items, expected %d\n", 518c87a7e75Speter enderborg items2, items); 5199e0bd4cbSDan Carpenter return -EINVAL; 520782ebb99SStephen Smalley } 521782ebb99SStephen Smalley return 0; 522782ebb99SStephen Smalley } 523782ebb99SStephen Smalley 524782ebb99SStephen Smalley rc = next_entry(buf16, fp, sizeof(u16)*4); 5259e0bd4cbSDan Carpenter if (rc) { 526c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 5279e0bd4cbSDan Carpenter return rc; 528782ebb99SStephen Smalley } 529782ebb99SStephen Smalley 530782ebb99SStephen Smalley items = 0; 531782ebb99SStephen Smalley key.source_type = le16_to_cpu(buf16[items++]); 532782ebb99SStephen Smalley key.target_type = le16_to_cpu(buf16[items++]); 533782ebb99SStephen Smalley key.target_class = le16_to_cpu(buf16[items++]); 534782ebb99SStephen Smalley key.specified = le16_to_cpu(buf16[items++]); 535782ebb99SStephen Smalley 53645e5421eSStephen Smalley if (!policydb_type_isvalid(pol, key.source_type) || 53745e5421eSStephen Smalley !policydb_type_isvalid(pol, key.target_type) || 53845e5421eSStephen Smalley !policydb_class_isvalid(pol, key.target_class)) { 539c87a7e75Speter enderborg pr_err("SELinux: avtab: invalid type or class\n"); 5409e0bd4cbSDan Carpenter return -EINVAL; 54145e5421eSStephen Smalley } 54245e5421eSStephen Smalley 54345e5421eSStephen Smalley set = 0; 54445e5421eSStephen Smalley for (i = 0; i < ARRAY_SIZE(spec_order); i++) { 54545e5421eSStephen Smalley if (key.specified & spec_order[i]) 54645e5421eSStephen Smalley set++; 54745e5421eSStephen Smalley } 54845e5421eSStephen Smalley if (!set || set > 1) { 549c87a7e75Speter enderborg pr_err("SELinux: avtab: more than one specifier\n"); 5509e0bd4cbSDan Carpenter return -EINVAL; 55145e5421eSStephen Smalley } 55245e5421eSStephen Smalley 553fa1aa143SJeff Vander Stoep if ((vers < POLICYDB_VERSION_XPERMS_IOCTL) && 554fa1aa143SJeff Vander Stoep (key.specified & AVTAB_XPERMS)) { 555c87a7e75Speter enderborg pr_err("SELinux: avtab: policy version %u does not " 556fa1aa143SJeff Vander Stoep "support extended permissions rules and one " 557fa1aa143SJeff Vander Stoep "was specified\n", vers); 558fa1aa143SJeff Vander Stoep return -EINVAL; 559fa1aa143SJeff Vander Stoep } else if (key.specified & AVTAB_XPERMS) { 560fa1aa143SJeff Vander Stoep memset(&xperms, 0, sizeof(struct avtab_extended_perms)); 561fa1aa143SJeff Vander Stoep rc = next_entry(&xperms.specified, fp, sizeof(u8)); 562fa1aa143SJeff Vander Stoep if (rc) { 563c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 564fa1aa143SJeff Vander Stoep return rc; 565fa1aa143SJeff Vander Stoep } 566fa1aa143SJeff Vander Stoep rc = next_entry(&xperms.driver, fp, sizeof(u8)); 567fa1aa143SJeff Vander Stoep if (rc) { 568c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 569fa1aa143SJeff Vander Stoep return rc; 570fa1aa143SJeff Vander Stoep } 571fa1aa143SJeff Vander Stoep rc = next_entry(buf32, fp, sizeof(u32)*ARRAY_SIZE(xperms.perms.p)); 572fa1aa143SJeff Vander Stoep if (rc) { 573c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 574fa1aa143SJeff Vander Stoep return rc; 575fa1aa143SJeff Vander Stoep } 576fa1aa143SJeff Vander Stoep for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++) 577fa1aa143SJeff Vander Stoep xperms.perms.p[i] = le32_to_cpu(buf32[i]); 578fa1aa143SJeff Vander Stoep datum.u.xperms = &xperms; 579fa1aa143SJeff Vander Stoep } else { 580782ebb99SStephen Smalley rc = next_entry(buf32, fp, sizeof(u32)); 5819e0bd4cbSDan Carpenter if (rc) { 582c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated entry\n"); 5839e0bd4cbSDan Carpenter return rc; 584782ebb99SStephen Smalley } 585fa1aa143SJeff Vander Stoep datum.u.data = le32_to_cpu(*buf32); 586fa1aa143SJeff Vander Stoep } 58745e5421eSStephen Smalley if ((key.specified & AVTAB_TYPE) && 588fa1aa143SJeff Vander Stoep !policydb_type_isvalid(pol, datum.u.data)) { 589c87a7e75Speter enderborg pr_err("SELinux: avtab: invalid type\n"); 5909e0bd4cbSDan Carpenter return -EINVAL; 59145e5421eSStephen Smalley } 592782ebb99SStephen Smalley return insertf(a, &key, &datum, p); 593782ebb99SStephen Smalley } 594782ebb99SStephen Smalley 595782ebb99SStephen Smalley static int avtab_insertf(struct avtab *a, struct avtab_key *k, 596782ebb99SStephen Smalley struct avtab_datum *d, void *p) 597782ebb99SStephen Smalley { 598782ebb99SStephen Smalley return avtab_insert(a, k, d); 599782ebb99SStephen Smalley } 600782ebb99SStephen Smalley 60145e5421eSStephen Smalley int avtab_read(struct avtab *a, void *fp, struct policydb *pol) 6021da177e4SLinus Torvalds { 6031da177e4SLinus Torvalds int rc; 604b5bf6c55SAlexey Dobriyan __le32 buf[1]; 6051da177e4SLinus Torvalds u32 nel, i; 6061da177e4SLinus Torvalds 6071da177e4SLinus Torvalds 6081da177e4SLinus Torvalds rc = next_entry(buf, fp, sizeof(u32)); 6091da177e4SLinus Torvalds if (rc < 0) { 610c87a7e75Speter enderborg pr_err("SELinux: avtab: truncated table\n"); 6111da177e4SLinus Torvalds goto bad; 6121da177e4SLinus Torvalds } 6131da177e4SLinus Torvalds nel = le32_to_cpu(buf[0]); 6141da177e4SLinus Torvalds if (!nel) { 615c87a7e75Speter enderborg pr_err("SELinux: avtab: table is empty\n"); 6161da177e4SLinus Torvalds rc = -EINVAL; 6171da177e4SLinus Torvalds goto bad; 6181da177e4SLinus Torvalds } 6193232c110SYuichi Nakamura 6203232c110SYuichi Nakamura rc = avtab_alloc(a, nel); 6213232c110SYuichi Nakamura if (rc) 6223232c110SYuichi Nakamura goto bad; 6233232c110SYuichi Nakamura 6241da177e4SLinus Torvalds for (i = 0; i < nel; i++) { 62545e5421eSStephen Smalley rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); 6261da177e4SLinus Torvalds if (rc) { 6271da177e4SLinus Torvalds if (rc == -ENOMEM) 628c87a7e75Speter enderborg pr_err("SELinux: avtab: out of memory\n"); 629782ebb99SStephen Smalley else if (rc == -EEXIST) 630c87a7e75Speter enderborg pr_err("SELinux: avtab: duplicate entry\n"); 6319e0bd4cbSDan Carpenter 6321da177e4SLinus Torvalds goto bad; 6331da177e4SLinus Torvalds } 6341da177e4SLinus Torvalds } 6351da177e4SLinus Torvalds 6361da177e4SLinus Torvalds rc = 0; 6371da177e4SLinus Torvalds out: 6381da177e4SLinus Torvalds return rc; 6391da177e4SLinus Torvalds 6401da177e4SLinus Torvalds bad: 6411da177e4SLinus Torvalds avtab_destroy(a); 6421da177e4SLinus Torvalds goto out; 6431da177e4SLinus Torvalds } 6441da177e4SLinus Torvalds 645cee74f47SEric Paris int avtab_write_item(struct policydb *p, struct avtab_node *cur, void *fp) 646cee74f47SEric Paris { 647cee74f47SEric Paris __le16 buf16[4]; 648fa1aa143SJeff Vander Stoep __le32 buf32[ARRAY_SIZE(cur->datum.u.xperms->perms.p)]; 649cee74f47SEric Paris int rc; 650fa1aa143SJeff Vander Stoep unsigned int i; 651cee74f47SEric Paris 652cee74f47SEric Paris buf16[0] = cpu_to_le16(cur->key.source_type); 653cee74f47SEric Paris buf16[1] = cpu_to_le16(cur->key.target_type); 654cee74f47SEric Paris buf16[2] = cpu_to_le16(cur->key.target_class); 655cee74f47SEric Paris buf16[3] = cpu_to_le16(cur->key.specified); 656cee74f47SEric Paris rc = put_entry(buf16, sizeof(u16), 4, fp); 657cee74f47SEric Paris if (rc) 658cee74f47SEric Paris return rc; 659fa1aa143SJeff Vander Stoep 660fa1aa143SJeff Vander Stoep if (cur->key.specified & AVTAB_XPERMS) { 661fa1aa143SJeff Vander Stoep rc = put_entry(&cur->datum.u.xperms->specified, sizeof(u8), 1, fp); 662fa1aa143SJeff Vander Stoep if (rc) 663fa1aa143SJeff Vander Stoep return rc; 664fa1aa143SJeff Vander Stoep rc = put_entry(&cur->datum.u.xperms->driver, sizeof(u8), 1, fp); 665fa1aa143SJeff Vander Stoep if (rc) 666fa1aa143SJeff Vander Stoep return rc; 667fa1aa143SJeff Vander Stoep for (i = 0; i < ARRAY_SIZE(cur->datum.u.xperms->perms.p); i++) 668fa1aa143SJeff Vander Stoep buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]); 669fa1aa143SJeff Vander Stoep rc = put_entry(buf32, sizeof(u32), 670fa1aa143SJeff Vander Stoep ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp); 671fa1aa143SJeff Vander Stoep } else { 672fa1aa143SJeff Vander Stoep buf32[0] = cpu_to_le32(cur->datum.u.data); 673cee74f47SEric Paris rc = put_entry(buf32, sizeof(u32), 1, fp); 674fa1aa143SJeff Vander Stoep } 675cee74f47SEric Paris if (rc) 676cee74f47SEric Paris return rc; 677cee74f47SEric Paris return 0; 678cee74f47SEric Paris } 679cee74f47SEric Paris 680cee74f47SEric Paris int avtab_write(struct policydb *p, struct avtab *a, void *fp) 681cee74f47SEric Paris { 682cee74f47SEric Paris unsigned int i; 683cee74f47SEric Paris int rc = 0; 684cee74f47SEric Paris struct avtab_node *cur; 685cee74f47SEric Paris __le32 buf[1]; 686cee74f47SEric Paris 687cee74f47SEric Paris buf[0] = cpu_to_le32(a->nel); 688cee74f47SEric Paris rc = put_entry(buf, sizeof(u32), 1, fp); 689cee74f47SEric Paris if (rc) 690cee74f47SEric Paris return rc; 691cee74f47SEric Paris 692cee74f47SEric Paris for (i = 0; i < a->nslot; i++) { 693acdf52d9SKent Overstreet for (cur = a->htable[i]; cur; 694ba39db6eSStephen Smalley cur = cur->next) { 695cee74f47SEric Paris rc = avtab_write_item(p, cur, fp); 696cee74f47SEric Paris if (rc) 697cee74f47SEric Paris return rc; 698cee74f47SEric Paris } 699cee74f47SEric Paris } 700cee74f47SEric Paris 701cee74f47SEric Paris return rc; 702cee74f47SEric Paris } 703aa8e712cSStephen Smalley 704aa8e712cSStephen Smalley void __init avtab_cache_init(void) 7051da177e4SLinus Torvalds { 7061da177e4SLinus Torvalds avtab_node_cachep = kmem_cache_create("avtab_node", 7071da177e4SLinus Torvalds sizeof(struct avtab_node), 70820c2df83SPaul Mundt 0, SLAB_PANIC, NULL); 709fa1aa143SJeff Vander Stoep avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms", 710fa1aa143SJeff Vander Stoep sizeof(struct avtab_extended_perms), 711fa1aa143SJeff Vander Stoep 0, SLAB_PANIC, NULL); 7121da177e4SLinus Torvalds } 713