1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Implementation of the SID table type. |
4 | * |
5 | * Original author: Stephen Smalley, <stephen.smalley.work@gmail.com> |
6 | * Author: Ondrej Mosnacek, <omosnacek@gmail.com> |
7 | * |
8 | * Copyright (C) 2018 Red Hat, Inc. |
9 | */ |
10 | #include <linux/errno.h> |
11 | #include <linux/kernel.h> |
12 | #include <linux/list.h> |
13 | #include <linux/rcupdate.h> |
14 | #include <linux/slab.h> |
15 | #include <linux/sched.h> |
16 | #include <linux/spinlock.h> |
17 | #include <asm/barrier.h> |
18 | #include "flask.h" |
19 | #include "security.h" |
20 | #include "sidtab.h" |
21 | #include "services.h" |
22 | |
23 | struct sidtab_str_cache { |
24 | struct rcu_head rcu_member; |
25 | struct list_head lru_member; |
26 | struct sidtab_entry *parent; |
27 | u32 len; |
28 | char str[] __counted_by(len); |
29 | }; |
30 | |
31 | #define index_to_sid(index) ((index) + SECINITSID_NUM + 1) |
32 | #define sid_to_index(sid) ((sid) - (SECINITSID_NUM + 1)) |
33 | |
34 | int sidtab_init(struct sidtab *s) |
35 | { |
36 | u32 i; |
37 | |
38 | memset(s->roots, 0, sizeof(s->roots)); |
39 | |
40 | for (i = 0; i < SECINITSID_NUM; i++) |
41 | s->isids[i].set = 0; |
42 | |
43 | s->frozen = false; |
44 | s->count = 0; |
45 | s->convert = NULL; |
46 | hash_init(s->context_to_sid); |
47 | |
48 | spin_lock_init(&s->lock); |
49 | |
50 | #if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0 |
51 | s->cache_free_slots = CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE; |
52 | INIT_LIST_HEAD(list: &s->cache_lru_list); |
53 | spin_lock_init(&s->cache_lock); |
54 | #endif |
55 | |
56 | return 0; |
57 | } |
58 | |
59 | static u32 context_to_sid(struct sidtab *s, struct context *context, u32 hash) |
60 | { |
61 | struct sidtab_entry *entry; |
62 | u32 sid = 0; |
63 | |
64 | rcu_read_lock(); |
65 | hash_for_each_possible_rcu(s->context_to_sid, entry, list, hash) { |
66 | if (entry->hash != hash) |
67 | continue; |
68 | if (context_cmp(c1: &entry->context, c2: context)) { |
69 | sid = entry->sid; |
70 | break; |
71 | } |
72 | } |
73 | rcu_read_unlock(); |
74 | return sid; |
75 | } |
76 | |
77 | int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context) |
78 | { |
79 | struct sidtab_isid_entry *isid; |
80 | u32 hash; |
81 | int rc; |
82 | |
83 | if (sid == 0 || sid > SECINITSID_NUM) |
84 | return -EINVAL; |
85 | |
86 | isid = &s->isids[sid - 1]; |
87 | |
88 | rc = context_cpy(dst: &isid->entry.context, src: context); |
89 | if (rc) |
90 | return rc; |
91 | |
92 | #if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0 |
93 | isid->entry.cache = NULL; |
94 | #endif |
95 | isid->set = 1; |
96 | |
97 | hash = context_compute_hash(c: context); |
98 | |
99 | /* |
100 | * Multiple initial sids may map to the same context. Check that this |
101 | * context is not already represented in the context_to_sid hashtable |
102 | * to avoid duplicate entries and long linked lists upon hash |
103 | * collision. |
104 | */ |
105 | if (!context_to_sid(s, context, hash)) { |
106 | isid->entry.sid = sid; |
107 | isid->entry.hash = hash; |
108 | hash_add(s->context_to_sid, &isid->entry.list, hash); |
109 | } |
110 | |
111 | return 0; |
112 | } |
113 | |
114 | int sidtab_hash_stats(struct sidtab *sidtab, char *page) |
115 | { |
116 | int i; |
117 | int chain_len = 0; |
118 | int slots_used = 0; |
119 | int entries = 0; |
120 | int max_chain_len = 0; |
121 | int cur_bucket = 0; |
122 | struct sidtab_entry *entry; |
123 | |
124 | rcu_read_lock(); |
125 | hash_for_each_rcu(sidtab->context_to_sid, i, entry, list) { |
126 | entries++; |
127 | if (i == cur_bucket) { |
128 | chain_len++; |
129 | if (chain_len == 1) |
130 | slots_used++; |
131 | } else { |
132 | cur_bucket = i; |
133 | if (chain_len > max_chain_len) |
134 | max_chain_len = chain_len; |
135 | chain_len = 0; |
136 | } |
137 | } |
138 | rcu_read_unlock(); |
139 | |
140 | if (chain_len > max_chain_len) |
141 | max_chain_len = chain_len; |
142 | |
143 | return scnprintf(buf: page, PAGE_SIZE, fmt: "entries: %d\nbuckets used: %d/%d\n" |
144 | "longest chain: %d\n" , entries, |
145 | slots_used, SIDTAB_HASH_BUCKETS, max_chain_len); |
146 | } |
147 | |
148 | static u32 sidtab_level_from_count(u32 count) |
149 | { |
150 | u32 capacity = SIDTAB_LEAF_ENTRIES; |
151 | u32 level = 0; |
152 | |
153 | while (count > capacity) { |
154 | capacity <<= SIDTAB_INNER_SHIFT; |
155 | ++level; |
156 | } |
157 | return level; |
158 | } |
159 | |
160 | static int sidtab_alloc_roots(struct sidtab *s, u32 level) |
161 | { |
162 | u32 l; |
163 | |
164 | if (!s->roots[0].ptr_leaf) { |
165 | s->roots[0].ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE, |
166 | GFP_ATOMIC); |
167 | if (!s->roots[0].ptr_leaf) |
168 | return -ENOMEM; |
169 | } |
170 | for (l = 1; l <= level; ++l) |
171 | if (!s->roots[l].ptr_inner) { |
172 | s->roots[l].ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE, |
173 | GFP_ATOMIC); |
174 | if (!s->roots[l].ptr_inner) |
175 | return -ENOMEM; |
176 | s->roots[l].ptr_inner->entries[0] = s->roots[l - 1]; |
177 | } |
178 | return 0; |
179 | } |
180 | |
181 | static struct sidtab_entry *sidtab_do_lookup(struct sidtab *s, u32 index, |
182 | int alloc) |
183 | { |
184 | union sidtab_entry_inner *entry; |
185 | u32 level, capacity_shift, leaf_index = index / SIDTAB_LEAF_ENTRIES; |
186 | |
187 | /* find the level of the subtree we need */ |
188 | level = sidtab_level_from_count(count: index + 1); |
189 | capacity_shift = level * SIDTAB_INNER_SHIFT; |
190 | |
191 | /* allocate roots if needed */ |
192 | if (alloc && sidtab_alloc_roots(s, level) != 0) |
193 | return NULL; |
194 | |
195 | /* lookup inside the subtree */ |
196 | entry = &s->roots[level]; |
197 | while (level != 0) { |
198 | capacity_shift -= SIDTAB_INNER_SHIFT; |
199 | --level; |
200 | |
201 | entry = &entry->ptr_inner->entries[leaf_index >> capacity_shift]; |
202 | leaf_index &= ((u32)1 << capacity_shift) - 1; |
203 | |
204 | if (!entry->ptr_inner) { |
205 | if (alloc) |
206 | entry->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE, |
207 | GFP_ATOMIC); |
208 | if (!entry->ptr_inner) |
209 | return NULL; |
210 | } |
211 | } |
212 | if (!entry->ptr_leaf) { |
213 | if (alloc) |
214 | entry->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE, |
215 | GFP_ATOMIC); |
216 | if (!entry->ptr_leaf) |
217 | return NULL; |
218 | } |
219 | return &entry->ptr_leaf->entries[index % SIDTAB_LEAF_ENTRIES]; |
220 | } |
221 | |
222 | static struct sidtab_entry *sidtab_lookup(struct sidtab *s, u32 index) |
223 | { |
224 | /* read entries only after reading count */ |
225 | u32 count = smp_load_acquire(&s->count); |
226 | |
227 | if (index >= count) |
228 | return NULL; |
229 | |
230 | return sidtab_do_lookup(s, index, alloc: 0); |
231 | } |
232 | |
233 | static struct sidtab_entry *sidtab_lookup_initial(struct sidtab *s, u32 sid) |
234 | { |
235 | return s->isids[sid - 1].set ? &s->isids[sid - 1].entry : NULL; |
236 | } |
237 | |
238 | static struct sidtab_entry *sidtab_search_core(struct sidtab *s, u32 sid, |
239 | int force) |
240 | { |
241 | if (sid != 0) { |
242 | struct sidtab_entry *entry; |
243 | |
244 | if (sid > SECINITSID_NUM) |
245 | entry = sidtab_lookup(s, sid_to_index(sid)); |
246 | else |
247 | entry = sidtab_lookup_initial(s, sid); |
248 | if (entry && (!entry->context.len || force)) |
249 | return entry; |
250 | } |
251 | |
252 | return sidtab_lookup_initial(s, sid: SECINITSID_UNLABELED); |
253 | } |
254 | |
255 | struct sidtab_entry *sidtab_search_entry(struct sidtab *s, u32 sid) |
256 | { |
257 | return sidtab_search_core(s, sid, force: 0); |
258 | } |
259 | |
260 | struct sidtab_entry *sidtab_search_entry_force(struct sidtab *s, u32 sid) |
261 | { |
262 | return sidtab_search_core(s, sid, force: 1); |
263 | } |
264 | |
265 | int sidtab_context_to_sid(struct sidtab *s, struct context *context, |
266 | u32 *sid) |
267 | { |
268 | unsigned long flags; |
269 | u32 count, hash = context_compute_hash(c: context); |
270 | struct sidtab_convert_params *convert; |
271 | struct sidtab_entry *dst, *dst_convert; |
272 | int rc; |
273 | |
274 | *sid = context_to_sid(s, context, hash); |
275 | if (*sid) |
276 | return 0; |
277 | |
278 | /* lock-free search failed: lock, re-search, and insert if not found */ |
279 | spin_lock_irqsave(&s->lock, flags); |
280 | |
281 | rc = 0; |
282 | *sid = context_to_sid(s, context, hash); |
283 | if (*sid) |
284 | goto out_unlock; |
285 | |
286 | if (unlikely(s->frozen)) { |
287 | /* |
288 | * This sidtab is now frozen - tell the caller to abort and |
289 | * get the new one. |
290 | */ |
291 | rc = -ESTALE; |
292 | goto out_unlock; |
293 | } |
294 | |
295 | count = s->count; |
296 | |
297 | /* bail out if we already reached max entries */ |
298 | rc = -EOVERFLOW; |
299 | if (count >= SIDTAB_MAX) |
300 | goto out_unlock; |
301 | |
302 | /* insert context into new entry */ |
303 | rc = -ENOMEM; |
304 | dst = sidtab_do_lookup(s, index: count, alloc: 1); |
305 | if (!dst) |
306 | goto out_unlock; |
307 | |
308 | dst->sid = index_to_sid(count); |
309 | dst->hash = hash; |
310 | |
311 | rc = context_cpy(dst: &dst->context, src: context); |
312 | if (rc) |
313 | goto out_unlock; |
314 | |
315 | /* |
316 | * if we are building a new sidtab, we need to convert the context |
317 | * and insert it there as well |
318 | */ |
319 | convert = s->convert; |
320 | if (convert) { |
321 | struct sidtab *target = convert->target; |
322 | |
323 | rc = -ENOMEM; |
324 | dst_convert = sidtab_do_lookup(s: target, index: count, alloc: 1); |
325 | if (!dst_convert) { |
326 | context_destroy(c: &dst->context); |
327 | goto out_unlock; |
328 | } |
329 | |
330 | rc = services_convert_context(args: convert->args, |
331 | oldc: context, newc: &dst_convert->context, |
332 | GFP_ATOMIC); |
333 | if (rc) { |
334 | context_destroy(c: &dst->context); |
335 | goto out_unlock; |
336 | } |
337 | dst_convert->sid = index_to_sid(count); |
338 | dst_convert->hash = context_compute_hash(c: &dst_convert->context); |
339 | target->count = count + 1; |
340 | |
341 | hash_add_rcu(target->context_to_sid, |
342 | &dst_convert->list, dst_convert->hash); |
343 | } |
344 | |
345 | if (context->len) |
346 | pr_info("SELinux: Context %s is not valid (left unmapped).\n" , |
347 | context->str); |
348 | |
349 | *sid = index_to_sid(count); |
350 | |
351 | /* write entries before updating count */ |
352 | smp_store_release(&s->count, count + 1); |
353 | hash_add_rcu(s->context_to_sid, &dst->list, dst->hash); |
354 | |
355 | rc = 0; |
356 | out_unlock: |
357 | spin_unlock_irqrestore(lock: &s->lock, flags); |
358 | return rc; |
359 | } |
360 | |
361 | static void sidtab_convert_hashtable(struct sidtab *s, u32 count) |
362 | { |
363 | struct sidtab_entry *entry; |
364 | u32 i; |
365 | |
366 | for (i = 0; i < count; i++) { |
367 | entry = sidtab_do_lookup(s, index: i, alloc: 0); |
368 | entry->sid = index_to_sid(i); |
369 | entry->hash = context_compute_hash(c: &entry->context); |
370 | |
371 | hash_add_rcu(s->context_to_sid, &entry->list, entry->hash); |
372 | } |
373 | } |
374 | |
375 | static int sidtab_convert_tree(union sidtab_entry_inner *edst, |
376 | union sidtab_entry_inner *esrc, |
377 | u32 *pos, u32 count, u32 level, |
378 | struct sidtab_convert_params *convert) |
379 | { |
380 | int rc; |
381 | u32 i; |
382 | |
383 | if (level != 0) { |
384 | if (!edst->ptr_inner) { |
385 | edst->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE, |
386 | GFP_KERNEL); |
387 | if (!edst->ptr_inner) |
388 | return -ENOMEM; |
389 | } |
390 | i = 0; |
391 | while (i < SIDTAB_INNER_ENTRIES && *pos < count) { |
392 | rc = sidtab_convert_tree(edst: &edst->ptr_inner->entries[i], |
393 | esrc: &esrc->ptr_inner->entries[i], |
394 | pos, count, level: level - 1, |
395 | convert); |
396 | if (rc) |
397 | return rc; |
398 | i++; |
399 | } |
400 | } else { |
401 | if (!edst->ptr_leaf) { |
402 | edst->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE, |
403 | GFP_KERNEL); |
404 | if (!edst->ptr_leaf) |
405 | return -ENOMEM; |
406 | } |
407 | i = 0; |
408 | while (i < SIDTAB_LEAF_ENTRIES && *pos < count) { |
409 | rc = services_convert_context(args: convert->args, |
410 | oldc: &esrc->ptr_leaf->entries[i].context, |
411 | newc: &edst->ptr_leaf->entries[i].context, |
412 | GFP_KERNEL); |
413 | if (rc) |
414 | return rc; |
415 | (*pos)++; |
416 | i++; |
417 | } |
418 | cond_resched(); |
419 | } |
420 | return 0; |
421 | } |
422 | |
423 | int sidtab_convert(struct sidtab *s, struct sidtab_convert_params *params) |
424 | { |
425 | unsigned long flags; |
426 | u32 count, level, pos; |
427 | int rc; |
428 | |
429 | spin_lock_irqsave(&s->lock, flags); |
430 | |
431 | /* concurrent policy loads are not allowed */ |
432 | if (s->convert) { |
433 | spin_unlock_irqrestore(lock: &s->lock, flags); |
434 | return -EBUSY; |
435 | } |
436 | |
437 | count = s->count; |
438 | level = sidtab_level_from_count(count); |
439 | |
440 | /* allocate last leaf in the new sidtab (to avoid race with |
441 | * live convert) |
442 | */ |
443 | rc = sidtab_do_lookup(s: params->target, index: count - 1, alloc: 1) ? 0 : -ENOMEM; |
444 | if (rc) { |
445 | spin_unlock_irqrestore(lock: &s->lock, flags); |
446 | return rc; |
447 | } |
448 | |
449 | /* set count in case no new entries are added during conversion */ |
450 | params->target->count = count; |
451 | |
452 | /* enable live convert of new entries */ |
453 | s->convert = params; |
454 | |
455 | /* we can safely convert the tree outside the lock */ |
456 | spin_unlock_irqrestore(lock: &s->lock, flags); |
457 | |
458 | pr_info("SELinux: Converting %u SID table entries...\n" , count); |
459 | |
460 | /* convert all entries not covered by live convert */ |
461 | pos = 0; |
462 | rc = sidtab_convert_tree(edst: ¶ms->target->roots[level], |
463 | esrc: &s->roots[level], pos: &pos, count, level, convert: params); |
464 | if (rc) { |
465 | /* we need to keep the old table - disable live convert */ |
466 | spin_lock_irqsave(&s->lock, flags); |
467 | s->convert = NULL; |
468 | spin_unlock_irqrestore(lock: &s->lock, flags); |
469 | return rc; |
470 | } |
471 | /* |
472 | * The hashtable can also be modified in sidtab_context_to_sid() |
473 | * so we must re-acquire the lock here. |
474 | */ |
475 | spin_lock_irqsave(&s->lock, flags); |
476 | sidtab_convert_hashtable(s: params->target, count); |
477 | spin_unlock_irqrestore(lock: &s->lock, flags); |
478 | |
479 | return 0; |
480 | } |
481 | |
482 | void sidtab_cancel_convert(struct sidtab *s) |
483 | { |
484 | unsigned long flags; |
485 | |
486 | /* cancelling policy load - disable live convert of sidtab */ |
487 | spin_lock_irqsave(&s->lock, flags); |
488 | s->convert = NULL; |
489 | spin_unlock_irqrestore(lock: &s->lock, flags); |
490 | } |
491 | |
492 | void sidtab_freeze_begin(struct sidtab *s, unsigned long *flags) __acquires(&s->lock) |
493 | { |
494 | spin_lock_irqsave(&s->lock, *flags); |
495 | s->frozen = true; |
496 | s->convert = NULL; |
497 | } |
498 | void sidtab_freeze_end(struct sidtab *s, unsigned long *flags) __releases(&s->lock) |
499 | { |
500 | spin_unlock_irqrestore(lock: &s->lock, flags: *flags); |
501 | } |
502 | |
503 | static void sidtab_destroy_entry(struct sidtab_entry *entry) |
504 | { |
505 | context_destroy(c: &entry->context); |
506 | #if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0 |
507 | kfree(rcu_dereference_raw(entry->cache)); |
508 | #endif |
509 | } |
510 | |
511 | static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level) |
512 | { |
513 | u32 i; |
514 | |
515 | if (level != 0) { |
516 | struct sidtab_node_inner *node = entry.ptr_inner; |
517 | |
518 | if (!node) |
519 | return; |
520 | |
521 | for (i = 0; i < SIDTAB_INNER_ENTRIES; i++) |
522 | sidtab_destroy_tree(entry: node->entries[i], level: level - 1); |
523 | kfree(objp: node); |
524 | } else { |
525 | struct sidtab_node_leaf *node = entry.ptr_leaf; |
526 | |
527 | if (!node) |
528 | return; |
529 | |
530 | for (i = 0; i < SIDTAB_LEAF_ENTRIES; i++) |
531 | sidtab_destroy_entry(entry: &node->entries[i]); |
532 | kfree(objp: node); |
533 | } |
534 | } |
535 | |
536 | void sidtab_destroy(struct sidtab *s) |
537 | { |
538 | u32 i, level; |
539 | |
540 | for (i = 0; i < SECINITSID_NUM; i++) |
541 | if (s->isids[i].set) |
542 | sidtab_destroy_entry(entry: &s->isids[i].entry); |
543 | |
544 | level = SIDTAB_MAX_LEVEL; |
545 | while (level && !s->roots[level].ptr_inner) |
546 | --level; |
547 | |
548 | sidtab_destroy_tree(entry: s->roots[level], level); |
549 | /* |
550 | * The context_to_sid hashtable's objects are all shared |
551 | * with the isids array and context tree, and so don't need |
552 | * to be cleaned up here. |
553 | */ |
554 | } |
555 | |
556 | #if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0 |
557 | |
558 | void sidtab_sid2str_put(struct sidtab *s, struct sidtab_entry *entry, |
559 | const char *str, u32 str_len) |
560 | { |
561 | struct sidtab_str_cache *cache, *victim = NULL; |
562 | unsigned long flags; |
563 | |
564 | /* do not cache invalid contexts */ |
565 | if (entry->context.len) |
566 | return; |
567 | |
568 | spin_lock_irqsave(&s->cache_lock, flags); |
569 | |
570 | cache = rcu_dereference_protected(entry->cache, |
571 | lockdep_is_held(&s->cache_lock)); |
572 | if (cache) { |
573 | /* entry in cache - just bump to the head of LRU list */ |
574 | list_move(list: &cache->lru_member, head: &s->cache_lru_list); |
575 | goto out_unlock; |
576 | } |
577 | |
578 | cache = kmalloc(struct_size(cache, str, str_len), GFP_ATOMIC); |
579 | if (!cache) |
580 | goto out_unlock; |
581 | |
582 | if (s->cache_free_slots == 0) { |
583 | /* pop a cache entry from the tail and free it */ |
584 | victim = container_of(s->cache_lru_list.prev, |
585 | struct sidtab_str_cache, lru_member); |
586 | list_del(entry: &victim->lru_member); |
587 | rcu_assign_pointer(victim->parent->cache, NULL); |
588 | } else { |
589 | s->cache_free_slots--; |
590 | } |
591 | cache->parent = entry; |
592 | cache->len = str_len; |
593 | memcpy(cache->str, str, str_len); |
594 | list_add(new: &cache->lru_member, head: &s->cache_lru_list); |
595 | |
596 | rcu_assign_pointer(entry->cache, cache); |
597 | |
598 | out_unlock: |
599 | spin_unlock_irqrestore(lock: &s->cache_lock, flags); |
600 | kfree_rcu(victim, rcu_member); |
601 | } |
602 | |
603 | int sidtab_sid2str_get(struct sidtab *s, struct sidtab_entry *entry, |
604 | char **out, u32 *out_len) |
605 | { |
606 | struct sidtab_str_cache *cache; |
607 | int rc = 0; |
608 | |
609 | if (entry->context.len) |
610 | return -ENOENT; /* do not cache invalid contexts */ |
611 | |
612 | rcu_read_lock(); |
613 | |
614 | cache = rcu_dereference(entry->cache); |
615 | if (!cache) { |
616 | rc = -ENOENT; |
617 | } else { |
618 | *out_len = cache->len; |
619 | if (out) { |
620 | *out = kmemdup(p: cache->str, size: cache->len, GFP_ATOMIC); |
621 | if (!*out) |
622 | rc = -ENOMEM; |
623 | } |
624 | } |
625 | |
626 | rcu_read_unlock(); |
627 | |
628 | if (!rc && out) |
629 | sidtab_sid2str_put(s, entry, str: *out, str_len: *out_len); |
630 | return rc; |
631 | } |
632 | |
633 | #endif /* CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0 */ |
634 | |