sidtab.c 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304
  1. /*
  2. * Implementation of the SID table type.
  3. *
  4. * Author : Stephen Smalley, <sds@epoch.ncsc.mil>
  5. */
  6. #include <linux/kernel.h>
  7. #include <linux/slab.h>
  8. #include <linux/spinlock.h>
  9. #include <linux/errno.h>
  10. #include "flask.h"
  11. #include "security.h"
  12. #include "sidtab.h"
  13. #define SIDTAB_HASH(sid) \
  14. (sid & SIDTAB_HASH_MASK)
  15. #define INIT_SIDTAB_LOCK(s) spin_lock_init(&s->lock)
  16. #define SIDTAB_LOCK(s, x) spin_lock_irqsave(&s->lock, x)
  17. #define SIDTAB_UNLOCK(s, x) spin_unlock_irqrestore(&s->lock, x)
  18. int sidtab_init(struct sidtab *s)
  19. {
  20. int i;
  21. s->htable = kmalloc(sizeof(*(s->htable)) * SIDTAB_SIZE, GFP_ATOMIC);
  22. if (!s->htable)
  23. return -ENOMEM;
  24. for (i = 0; i < SIDTAB_SIZE; i++)
  25. s->htable[i] = NULL;
  26. s->nel = 0;
  27. s->next_sid = 1;
  28. s->shutdown = 0;
  29. INIT_SIDTAB_LOCK(s);
  30. return 0;
  31. }
  32. int sidtab_insert(struct sidtab *s, u32 sid, struct context *context)
  33. {
  34. int hvalue, rc = 0;
  35. struct sidtab_node *prev, *cur, *newnode;
  36. if (!s) {
  37. rc = -ENOMEM;
  38. goto out;
  39. }
  40. hvalue = SIDTAB_HASH(sid);
  41. prev = NULL;
  42. cur = s->htable[hvalue];
  43. while (cur != NULL && sid > cur->sid) {
  44. prev = cur;
  45. cur = cur->next;
  46. }
  47. if (cur && sid == cur->sid) {
  48. rc = -EEXIST;
  49. goto out;
  50. }
  51. newnode = kmalloc(sizeof(*newnode), GFP_ATOMIC);
  52. if (newnode == NULL) {
  53. rc = -ENOMEM;
  54. goto out;
  55. }
  56. newnode->sid = sid;
  57. if (context_cpy(&newnode->context, context)) {
  58. kfree(newnode);
  59. rc = -ENOMEM;
  60. goto out;
  61. }
  62. if (prev) {
  63. newnode->next = prev->next;
  64. wmb();
  65. prev->next = newnode;
  66. } else {
  67. newnode->next = s->htable[hvalue];
  68. wmb();
  69. s->htable[hvalue] = newnode;
  70. }
  71. s->nel++;
  72. if (sid >= s->next_sid)
  73. s->next_sid = sid + 1;
  74. out:
  75. return rc;
  76. }
  77. struct context *sidtab_search(struct sidtab *s, u32 sid)
  78. {
  79. int hvalue;
  80. struct sidtab_node *cur;
  81. if (!s)
  82. return NULL;
  83. hvalue = SIDTAB_HASH(sid);
  84. cur = s->htable[hvalue];
  85. while (cur != NULL && sid > cur->sid)
  86. cur = cur->next;
  87. if (cur == NULL || sid != cur->sid) {
  88. /* Remap invalid SIDs to the unlabeled SID. */
  89. sid = SECINITSID_UNLABELED;
  90. hvalue = SIDTAB_HASH(sid);
  91. cur = s->htable[hvalue];
  92. while (cur != NULL && sid > cur->sid)
  93. cur = cur->next;
  94. if (!cur || sid != cur->sid)
  95. return NULL;
  96. }
  97. return &cur->context;
  98. }
  99. int sidtab_map(struct sidtab *s,
  100. int (*apply) (u32 sid,
  101. struct context *context,
  102. void *args),
  103. void *args)
  104. {
  105. int i, rc = 0;
  106. struct sidtab_node *cur;
  107. if (!s)
  108. goto out;
  109. for (i = 0; i < SIDTAB_SIZE; i++) {
  110. cur = s->htable[i];
  111. while (cur != NULL) {
  112. rc = apply(cur->sid, &cur->context, args);
  113. if (rc)
  114. goto out;
  115. cur = cur->next;
  116. }
  117. }
  118. out:
  119. return rc;
  120. }
  121. void sidtab_map_remove_on_error(struct sidtab *s,
  122. int (*apply) (u32 sid,
  123. struct context *context,
  124. void *args),
  125. void *args)
  126. {
  127. int i, ret;
  128. struct sidtab_node *last, *cur, *temp;
  129. if (!s)
  130. return;
  131. for (i = 0; i < SIDTAB_SIZE; i++) {
  132. last = NULL;
  133. cur = s->htable[i];
  134. while (cur != NULL) {
  135. ret = apply(cur->sid, &cur->context, args);
  136. if (ret) {
  137. if (last) {
  138. last->next = cur->next;
  139. } else {
  140. s->htable[i] = cur->next;
  141. }
  142. temp = cur;
  143. cur = cur->next;
  144. context_destroy(&temp->context);
  145. kfree(temp);
  146. s->nel--;
  147. } else {
  148. last = cur;
  149. cur = cur->next;
  150. }
  151. }
  152. }
  153. return;
  154. }
  155. static inline u32 sidtab_search_context(struct sidtab *s,
  156. struct context *context)
  157. {
  158. int i;
  159. struct sidtab_node *cur;
  160. for (i = 0; i < SIDTAB_SIZE; i++) {
  161. cur = s->htable[i];
  162. while (cur != NULL) {
  163. if (context_cmp(&cur->context, context))
  164. return cur->sid;
  165. cur = cur->next;
  166. }
  167. }
  168. return 0;
  169. }
  170. int sidtab_context_to_sid(struct sidtab *s,
  171. struct context *context,
  172. u32 *out_sid)
  173. {
  174. u32 sid;
  175. int ret = 0;
  176. unsigned long flags;
  177. *out_sid = SECSID_NULL;
  178. sid = sidtab_search_context(s, context);
  179. if (!sid) {
  180. SIDTAB_LOCK(s, flags);
  181. /* Rescan now that we hold the lock. */
  182. sid = sidtab_search_context(s, context);
  183. if (sid)
  184. goto unlock_out;
  185. /* No SID exists for the context. Allocate a new one. */
  186. if (s->next_sid == UINT_MAX || s->shutdown) {
  187. ret = -ENOMEM;
  188. goto unlock_out;
  189. }
  190. sid = s->next_sid++;
  191. ret = sidtab_insert(s, sid, context);
  192. if (ret)
  193. s->next_sid--;
  194. unlock_out:
  195. SIDTAB_UNLOCK(s, flags);
  196. }
  197. if (ret)
  198. return ret;
  199. *out_sid = sid;
  200. return 0;
  201. }
  202. void sidtab_hash_eval(struct sidtab *h, char *tag)
  203. {
  204. int i, chain_len, slots_used, max_chain_len;
  205. struct sidtab_node *cur;
  206. slots_used = 0;
  207. max_chain_len = 0;
  208. for (i = 0; i < SIDTAB_SIZE; i++) {
  209. cur = h->htable[i];
  210. if (cur) {
  211. slots_used++;
  212. chain_len = 0;
  213. while (cur) {
  214. chain_len++;
  215. cur = cur->next;
  216. }
  217. if (chain_len > max_chain_len)
  218. max_chain_len = chain_len;
  219. }
  220. }
  221. printk(KERN_DEBUG "%s: %d entries and %d/%d buckets used, longest "
  222. "chain length %d\n", tag, h->nel, slots_used, SIDTAB_SIZE,
  223. max_chain_len);
  224. }
  225. void sidtab_destroy(struct sidtab *s)
  226. {
  227. int i;
  228. struct sidtab_node *cur, *temp;
  229. if (!s)
  230. return;
  231. for (i = 0; i < SIDTAB_SIZE; i++) {
  232. cur = s->htable[i];
  233. while (cur != NULL) {
  234. temp = cur;
  235. cur = cur->next;
  236. context_destroy(&temp->context);
  237. kfree(temp);
  238. }
  239. s->htable[i] = NULL;
  240. }
  241. kfree(s->htable);
  242. s->htable = NULL;
  243. s->nel = 0;
  244. s->next_sid = 1;
  245. }
  246. void sidtab_set(struct sidtab *dst, struct sidtab *src)
  247. {
  248. unsigned long flags;
  249. SIDTAB_LOCK(src, flags);
  250. dst->htable = src->htable;
  251. dst->nel = src->nel;
  252. dst->next_sid = src->next_sid;
  253. dst->shutdown = 0;
  254. SIDTAB_UNLOCK(src, flags);
  255. }
  256. void sidtab_shutdown(struct sidtab *s)
  257. {
  258. unsigned long flags;
  259. SIDTAB_LOCK(s, flags);
  260. s->shutdown = 1;
  261. SIDTAB_UNLOCK(s, flags);
  262. }