avtab.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454
  1. /*
  2. * Implementation of the access vector table type.
  3. *
  4. * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
  5. */
  6. /* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com>
  7. *
  8. * Added conditional policy language extensions
  9. *
  10. * Copyright (C) 2003 Tresys Technology, LLC
  11. * This program is free software; you can redistribute it and/or modify
  12. * it under the terms of the GNU General Public License as published by
  13. * the Free Software Foundation, version 2.
  14. */
  15. #include <linux/kernel.h>
  16. #include <linux/slab.h>
  17. #include <linux/vmalloc.h>
  18. #include <linux/errno.h>
  19. #include "avtab.h"
  20. #include "policydb.h"
  21. #define AVTAB_HASH(keyp) \
  22. ((keyp->target_class + \
  23. (keyp->target_type << 2) + \
  24. (keyp->source_type << 9)) & \
  25. AVTAB_HASH_MASK)
  26. static struct kmem_cache *avtab_node_cachep;
  27. static struct avtab_node*
  28. avtab_insert_node(struct avtab *h, int hvalue,
  29. struct avtab_node * prev, struct avtab_node * cur,
  30. struct avtab_key *key, struct avtab_datum *datum)
  31. {
  32. struct avtab_node * newnode;
  33. newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
  34. if (newnode == NULL)
  35. return NULL;
  36. newnode->key = *key;
  37. newnode->datum = *datum;
  38. if (prev) {
  39. newnode->next = prev->next;
  40. prev->next = newnode;
  41. } else {
  42. newnode->next = h->htable[hvalue];
  43. h->htable[hvalue] = newnode;
  44. }
  45. h->nel++;
  46. return newnode;
  47. }
  48. static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_datum *datum)
  49. {
  50. int hvalue;
  51. struct avtab_node *prev, *cur, *newnode;
  52. u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
  53. if (!h)
  54. return -EINVAL;
  55. hvalue = AVTAB_HASH(key);
  56. for (prev = NULL, cur = h->htable[hvalue];
  57. cur;
  58. prev = cur, cur = cur->next) {
  59. if (key->source_type == cur->key.source_type &&
  60. key->target_type == cur->key.target_type &&
  61. key->target_class == cur->key.target_class &&
  62. (specified & cur->key.specified))
  63. return -EEXIST;
  64. if (key->source_type < cur->key.source_type)
  65. break;
  66. if (key->source_type == cur->key.source_type &&
  67. key->target_type < cur->key.target_type)
  68. break;
  69. if (key->source_type == cur->key.source_type &&
  70. key->target_type == cur->key.target_type &&
  71. key->target_class < cur->key.target_class)
  72. break;
  73. }
  74. newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
  75. if(!newnode)
  76. return -ENOMEM;
  77. return 0;
  78. }
  79. /* Unlike avtab_insert(), this function allow multiple insertions of the same
  80. * key/specified mask into the table, as needed by the conditional avtab.
  81. * It also returns a pointer to the node inserted.
  82. */
  83. struct avtab_node *
  84. avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_datum * datum)
  85. {
  86. int hvalue;
  87. struct avtab_node *prev, *cur, *newnode;
  88. u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
  89. if (!h)
  90. return NULL;
  91. hvalue = AVTAB_HASH(key);
  92. for (prev = NULL, cur = h->htable[hvalue];
  93. cur;
  94. prev = cur, cur = cur->next) {
  95. if (key->source_type == cur->key.source_type &&
  96. key->target_type == cur->key.target_type &&
  97. key->target_class == cur->key.target_class &&
  98. (specified & cur->key.specified))
  99. break;
  100. if (key->source_type < cur->key.source_type)
  101. break;
  102. if (key->source_type == cur->key.source_type &&
  103. key->target_type < cur->key.target_type)
  104. break;
  105. if (key->source_type == cur->key.source_type &&
  106. key->target_type == cur->key.target_type &&
  107. key->target_class < cur->key.target_class)
  108. break;
  109. }
  110. newnode = avtab_insert_node(h, hvalue, prev, cur, key, datum);
  111. return newnode;
  112. }
  113. struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
  114. {
  115. int hvalue;
  116. struct avtab_node *cur;
  117. u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
  118. if (!h)
  119. return NULL;
  120. hvalue = AVTAB_HASH(key);
  121. for (cur = h->htable[hvalue]; cur; cur = cur->next) {
  122. if (key->source_type == cur->key.source_type &&
  123. key->target_type == cur->key.target_type &&
  124. key->target_class == cur->key.target_class &&
  125. (specified & cur->key.specified))
  126. return &cur->datum;
  127. if (key->source_type < cur->key.source_type)
  128. break;
  129. if (key->source_type == cur->key.source_type &&
  130. key->target_type < cur->key.target_type)
  131. break;
  132. if (key->source_type == cur->key.source_type &&
  133. key->target_type == cur->key.target_type &&
  134. key->target_class < cur->key.target_class)
  135. break;
  136. }
  137. return NULL;
  138. }
  139. /* This search function returns a node pointer, and can be used in
  140. * conjunction with avtab_search_next_node()
  141. */
  142. struct avtab_node*
  143. avtab_search_node(struct avtab *h, struct avtab_key *key)
  144. {
  145. int hvalue;
  146. struct avtab_node *cur;
  147. u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
  148. if (!h)
  149. return NULL;
  150. hvalue = AVTAB_HASH(key);
  151. for (cur = h->htable[hvalue]; cur; cur = cur->next) {
  152. if (key->source_type == cur->key.source_type &&
  153. key->target_type == cur->key.target_type &&
  154. key->target_class == cur->key.target_class &&
  155. (specified & cur->key.specified))
  156. return cur;
  157. if (key->source_type < cur->key.source_type)
  158. break;
  159. if (key->source_type == cur->key.source_type &&
  160. key->target_type < cur->key.target_type)
  161. break;
  162. if (key->source_type == cur->key.source_type &&
  163. key->target_type == cur->key.target_type &&
  164. key->target_class < cur->key.target_class)
  165. break;
  166. }
  167. return NULL;
  168. }
  169. struct avtab_node*
  170. avtab_search_node_next(struct avtab_node *node, int specified)
  171. {
  172. struct avtab_node *cur;
  173. if (!node)
  174. return NULL;
  175. specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
  176. for (cur = node->next; cur; cur = cur->next) {
  177. if (node->key.source_type == cur->key.source_type &&
  178. node->key.target_type == cur->key.target_type &&
  179. node->key.target_class == cur->key.target_class &&
  180. (specified & cur->key.specified))
  181. return cur;
  182. if (node->key.source_type < cur->key.source_type)
  183. break;
  184. if (node->key.source_type == cur->key.source_type &&
  185. node->key.target_type < cur->key.target_type)
  186. break;
  187. if (node->key.source_type == cur->key.source_type &&
  188. node->key.target_type == cur->key.target_type &&
  189. node->key.target_class < cur->key.target_class)
  190. break;
  191. }
  192. return NULL;
  193. }
  194. void avtab_destroy(struct avtab *h)
  195. {
  196. int i;
  197. struct avtab_node *cur, *temp;
  198. if (!h || !h->htable)
  199. return;
  200. for (i = 0; i < AVTAB_SIZE; i++) {
  201. cur = h->htable[i];
  202. while (cur != NULL) {
  203. temp = cur;
  204. cur = cur->next;
  205. kmem_cache_free(avtab_node_cachep, temp);
  206. }
  207. h->htable[i] = NULL;
  208. }
  209. vfree(h->htable);
  210. h->htable = NULL;
  211. }
  212. int avtab_init(struct avtab *h)
  213. {
  214. int i;
  215. h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
  216. if (!h->htable)
  217. return -ENOMEM;
  218. for (i = 0; i < AVTAB_SIZE; i++)
  219. h->htable[i] = NULL;
  220. h->nel = 0;
  221. return 0;
  222. }
  223. void avtab_hash_eval(struct avtab *h, char *tag)
  224. {
  225. int i, chain_len, slots_used, max_chain_len;
  226. struct avtab_node *cur;
  227. slots_used = 0;
  228. max_chain_len = 0;
  229. for (i = 0; i < AVTAB_SIZE; i++) {
  230. cur = h->htable[i];
  231. if (cur) {
  232. slots_used++;
  233. chain_len = 0;
  234. while (cur) {
  235. chain_len++;
  236. cur = cur->next;
  237. }
  238. if (chain_len > max_chain_len)
  239. max_chain_len = chain_len;
  240. }
  241. }
  242. printk(KERN_DEBUG "%s: %d entries and %d/%d buckets used, longest "
  243. "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
  244. max_chain_len);
  245. }
  246. static uint16_t spec_order[] = {
  247. AVTAB_ALLOWED,
  248. AVTAB_AUDITDENY,
  249. AVTAB_AUDITALLOW,
  250. AVTAB_TRANSITION,
  251. AVTAB_CHANGE,
  252. AVTAB_MEMBER
  253. };
  254. int avtab_read_item(void *fp, u32 vers, struct avtab *a,
  255. int (*insertf)(struct avtab *a, struct avtab_key *k,
  256. struct avtab_datum *d, void *p),
  257. void *p)
  258. {
  259. __le16 buf16[4];
  260. u16 enabled;
  261. __le32 buf32[7];
  262. u32 items, items2, val;
  263. struct avtab_key key;
  264. struct avtab_datum datum;
  265. int i, rc;
  266. memset(&key, 0, sizeof(struct avtab_key));
  267. memset(&datum, 0, sizeof(struct avtab_datum));
  268. if (vers < POLICYDB_VERSION_AVTAB) {
  269. rc = next_entry(buf32, fp, sizeof(u32));
  270. if (rc < 0) {
  271. printk(KERN_ERR "security: avtab: truncated entry\n");
  272. return -1;
  273. }
  274. items2 = le32_to_cpu(buf32[0]);
  275. if (items2 > ARRAY_SIZE(buf32)) {
  276. printk(KERN_ERR "security: avtab: entry overflow\n");
  277. return -1;
  278. }
  279. rc = next_entry(buf32, fp, sizeof(u32)*items2);
  280. if (rc < 0) {
  281. printk(KERN_ERR "security: avtab: truncated entry\n");
  282. return -1;
  283. }
  284. items = 0;
  285. val = le32_to_cpu(buf32[items++]);
  286. key.source_type = (u16)val;
  287. if (key.source_type != val) {
  288. printk("security: avtab: truncated source type\n");
  289. return -1;
  290. }
  291. val = le32_to_cpu(buf32[items++]);
  292. key.target_type = (u16)val;
  293. if (key.target_type != val) {
  294. printk("security: avtab: truncated target type\n");
  295. return -1;
  296. }
  297. val = le32_to_cpu(buf32[items++]);
  298. key.target_class = (u16)val;
  299. if (key.target_class != val) {
  300. printk("security: avtab: truncated target class\n");
  301. return -1;
  302. }
  303. val = le32_to_cpu(buf32[items++]);
  304. enabled = (val & AVTAB_ENABLED_OLD) ? AVTAB_ENABLED : 0;
  305. if (!(val & (AVTAB_AV | AVTAB_TYPE))) {
  306. printk("security: avtab: null entry\n");
  307. return -1;
  308. }
  309. if ((val & AVTAB_AV) &&
  310. (val & AVTAB_TYPE)) {
  311. printk("security: avtab: entry has both access vectors and types\n");
  312. return -1;
  313. }
  314. for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
  315. if (val & spec_order[i]) {
  316. key.specified = spec_order[i] | enabled;
  317. datum.data = le32_to_cpu(buf32[items++]);
  318. rc = insertf(a, &key, &datum, p);
  319. if (rc) return rc;
  320. }
  321. }
  322. if (items != items2) {
  323. printk("security: avtab: entry only had %d items, expected %d\n", items2, items);
  324. return -1;
  325. }
  326. return 0;
  327. }
  328. rc = next_entry(buf16, fp, sizeof(u16)*4);
  329. if (rc < 0) {
  330. printk("security: avtab: truncated entry\n");
  331. return -1;
  332. }
  333. items = 0;
  334. key.source_type = le16_to_cpu(buf16[items++]);
  335. key.target_type = le16_to_cpu(buf16[items++]);
  336. key.target_class = le16_to_cpu(buf16[items++]);
  337. key.specified = le16_to_cpu(buf16[items++]);
  338. rc = next_entry(buf32, fp, sizeof(u32));
  339. if (rc < 0) {
  340. printk("security: avtab: truncated entry\n");
  341. return -1;
  342. }
  343. datum.data = le32_to_cpu(*buf32);
  344. return insertf(a, &key, &datum, p);
  345. }
  346. static int avtab_insertf(struct avtab *a, struct avtab_key *k,
  347. struct avtab_datum *d, void *p)
  348. {
  349. return avtab_insert(a, k, d);
  350. }
  351. int avtab_read(struct avtab *a, void *fp, u32 vers)
  352. {
  353. int rc;
  354. __le32 buf[1];
  355. u32 nel, i;
  356. rc = next_entry(buf, fp, sizeof(u32));
  357. if (rc < 0) {
  358. printk(KERN_ERR "security: avtab: truncated table\n");
  359. goto bad;
  360. }
  361. nel = le32_to_cpu(buf[0]);
  362. if (!nel) {
  363. printk(KERN_ERR "security: avtab: table is empty\n");
  364. rc = -EINVAL;
  365. goto bad;
  366. }
  367. for (i = 0; i < nel; i++) {
  368. rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
  369. if (rc) {
  370. if (rc == -ENOMEM)
  371. printk(KERN_ERR "security: avtab: out of memory\n");
  372. else if (rc == -EEXIST)
  373. printk(KERN_ERR "security: avtab: duplicate entry\n");
  374. else
  375. rc = -EINVAL;
  376. goto bad;
  377. }
  378. }
  379. rc = 0;
  380. out:
  381. return rc;
  382. bad:
  383. avtab_destroy(a);
  384. goto out;
  385. }
  386. void avtab_cache_init(void)
  387. {
  388. avtab_node_cachep = kmem_cache_create("avtab_node",
  389. sizeof(struct avtab_node),
  390. 0, SLAB_PANIC, NULL, NULL);
  391. }
  392. void avtab_cache_destroy(void)
  393. {
  394. kmem_cache_destroy (avtab_node_cachep);
  395. }