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