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