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