Lines Matching +full:cache +full:- +full:level
1 // SPDX-License-Identifier: GPL-2.0
31 #define sid_to_index(sid) (sid - (SECINITSID_NUM + 1))
37 memset(s->roots, 0, sizeof(s->roots)); in sidtab_init()
40 s->isids[i].set = 0; in sidtab_init()
42 s->frozen = false; in sidtab_init()
43 s->count = 0; in sidtab_init()
44 s->convert = NULL; in sidtab_init()
45 hash_init(s->context_to_sid); in sidtab_init()
47 spin_lock_init(&s->lock); in sidtab_init()
50 s->cache_free_slots = CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE; in sidtab_init()
51 INIT_LIST_HEAD(&s->cache_lru_list); in sidtab_init()
52 spin_lock_init(&s->cache_lock); in sidtab_init()
64 hash_for_each_possible_rcu(s->context_to_sid, entry, list, hash) { in context_to_sid()
65 if (entry->hash != hash) in context_to_sid()
67 if (context_cmp(&entry->context, context)) { in context_to_sid()
68 sid = entry->sid; in context_to_sid()
83 return -EINVAL; in sidtab_set_initial()
85 isid = &s->isids[sid - 1]; in sidtab_set_initial()
87 rc = context_cpy(&isid->entry.context, context); in sidtab_set_initial()
92 isid->entry.cache = NULL; in sidtab_set_initial()
94 isid->set = 1; in sidtab_set_initial()
105 isid->entry.sid = sid; in sidtab_set_initial()
106 isid->entry.hash = hash; in sidtab_set_initial()
107 hash_add(s->context_to_sid, &isid->entry.list, hash); in sidtab_set_initial()
124 hash_for_each_rcu(sidtab->context_to_sid, i, entry, list) { in sidtab_hash_stats()
150 u32 level = 0; in sidtab_level_from_count() local
154 ++level; in sidtab_level_from_count()
156 return level; in sidtab_level_from_count()
159 static int sidtab_alloc_roots(struct sidtab *s, u32 level) in sidtab_alloc_roots() argument
163 if (!s->roots[0].ptr_leaf) { in sidtab_alloc_roots()
164 s->roots[0].ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE, in sidtab_alloc_roots()
166 if (!s->roots[0].ptr_leaf) in sidtab_alloc_roots()
167 return -ENOMEM; in sidtab_alloc_roots()
169 for (l = 1; l <= level; ++l) in sidtab_alloc_roots()
170 if (!s->roots[l].ptr_inner) { in sidtab_alloc_roots()
171 s->roots[l].ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE, in sidtab_alloc_roots()
173 if (!s->roots[l].ptr_inner) in sidtab_alloc_roots()
174 return -ENOMEM; in sidtab_alloc_roots()
175 s->roots[l].ptr_inner->entries[0] = s->roots[l - 1]; in sidtab_alloc_roots()
184 u32 level, capacity_shift, leaf_index = index / SIDTAB_LEAF_ENTRIES; in sidtab_do_lookup() local
186 /* find the level of the subtree we need */ in sidtab_do_lookup()
187 level = sidtab_level_from_count(index + 1); in sidtab_do_lookup()
188 capacity_shift = level * SIDTAB_INNER_SHIFT; in sidtab_do_lookup()
191 if (alloc && sidtab_alloc_roots(s, level) != 0) in sidtab_do_lookup()
195 entry = &s->roots[level]; in sidtab_do_lookup()
196 while (level != 0) { in sidtab_do_lookup()
197 capacity_shift -= SIDTAB_INNER_SHIFT; in sidtab_do_lookup()
198 --level; in sidtab_do_lookup()
200 entry = &entry->ptr_inner->entries[leaf_index >> capacity_shift]; in sidtab_do_lookup()
201 leaf_index &= ((u32)1 << capacity_shift) - 1; in sidtab_do_lookup()
203 if (!entry->ptr_inner) { in sidtab_do_lookup()
205 entry->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE, in sidtab_do_lookup()
207 if (!entry->ptr_inner) in sidtab_do_lookup()
211 if (!entry->ptr_leaf) { in sidtab_do_lookup()
213 entry->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE, in sidtab_do_lookup()
215 if (!entry->ptr_leaf) in sidtab_do_lookup()
218 return &entry->ptr_leaf->entries[index % SIDTAB_LEAF_ENTRIES]; in sidtab_do_lookup()
224 u32 count = smp_load_acquire(&s->count); in sidtab_lookup()
234 return s->isids[sid - 1].set ? &s->isids[sid - 1].entry : NULL; in sidtab_lookup_initial()
247 if (entry && (!entry->context.len || force)) in sidtab_search_core()
277 /* lock-free search failed: lock, re-search, and insert if not found */ in sidtab_context_to_sid()
278 spin_lock_irqsave(&s->lock, flags); in sidtab_context_to_sid()
285 if (unlikely(s->frozen)) { in sidtab_context_to_sid()
287 * This sidtab is now frozen - tell the caller to abort and in sidtab_context_to_sid()
290 rc = -ESTALE; in sidtab_context_to_sid()
294 count = s->count; in sidtab_context_to_sid()
295 convert = s->convert; in sidtab_context_to_sid()
298 rc = -EOVERFLOW; in sidtab_context_to_sid()
303 rc = -ENOMEM; in sidtab_context_to_sid()
308 dst->sid = index_to_sid(count); in sidtab_context_to_sid()
309 dst->hash = hash; in sidtab_context_to_sid()
311 rc = context_cpy(&dst->context, context); in sidtab_context_to_sid()
320 rc = -ENOMEM; in sidtab_context_to_sid()
321 dst_convert = sidtab_do_lookup(convert->target, count, 1); in sidtab_context_to_sid()
323 context_destroy(&dst->context); in sidtab_context_to_sid()
327 rc = convert->func(context, &dst_convert->context, in sidtab_context_to_sid()
328 convert->args); in sidtab_context_to_sid()
330 context_destroy(&dst->context); in sidtab_context_to_sid()
333 dst_convert->sid = index_to_sid(count); in sidtab_context_to_sid()
334 dst_convert->hash = context_compute_hash(&dst_convert->context); in sidtab_context_to_sid()
335 convert->target->count = count + 1; in sidtab_context_to_sid()
337 hash_add_rcu(convert->target->context_to_sid, in sidtab_context_to_sid()
338 &dst_convert->list, dst_convert->hash); in sidtab_context_to_sid()
341 if (context->len) in sidtab_context_to_sid()
343 context->str); in sidtab_context_to_sid()
348 smp_store_release(&s->count, count + 1); in sidtab_context_to_sid()
349 hash_add_rcu(s->context_to_sid, &dst->list, dst->hash); in sidtab_context_to_sid()
353 spin_unlock_irqrestore(&s->lock, flags); in sidtab_context_to_sid()
364 entry->sid = index_to_sid(i); in sidtab_convert_hashtable()
365 entry->hash = context_compute_hash(&entry->context); in sidtab_convert_hashtable()
367 hash_add_rcu(s->context_to_sid, &entry->list, entry->hash); in sidtab_convert_hashtable()
373 u32 *pos, u32 count, u32 level, in sidtab_convert_tree() argument
379 if (level != 0) { in sidtab_convert_tree()
380 if (!edst->ptr_inner) { in sidtab_convert_tree()
381 edst->ptr_inner = kzalloc(SIDTAB_NODE_ALLOC_SIZE, in sidtab_convert_tree()
383 if (!edst->ptr_inner) in sidtab_convert_tree()
384 return -ENOMEM; in sidtab_convert_tree()
388 rc = sidtab_convert_tree(&edst->ptr_inner->entries[i], in sidtab_convert_tree()
389 &esrc->ptr_inner->entries[i], in sidtab_convert_tree()
390 pos, count, level - 1, in sidtab_convert_tree()
397 if (!edst->ptr_leaf) { in sidtab_convert_tree()
398 edst->ptr_leaf = kzalloc(SIDTAB_NODE_ALLOC_SIZE, in sidtab_convert_tree()
400 if (!edst->ptr_leaf) in sidtab_convert_tree()
401 return -ENOMEM; in sidtab_convert_tree()
405 rc = convert->func(&esrc->ptr_leaf->entries[i].context, in sidtab_convert_tree()
406 &edst->ptr_leaf->entries[i].context, in sidtab_convert_tree()
407 convert->args); in sidtab_convert_tree()
421 u32 count, level, pos; in sidtab_convert() local
424 spin_lock_irqsave(&s->lock, flags); in sidtab_convert()
427 if (s->convert) { in sidtab_convert()
428 spin_unlock_irqrestore(&s->lock, flags); in sidtab_convert()
429 return -EBUSY; in sidtab_convert()
432 count = s->count; in sidtab_convert()
433 level = sidtab_level_from_count(count); in sidtab_convert()
438 rc = sidtab_do_lookup(params->target, count - 1, 1) ? 0 : -ENOMEM; in sidtab_convert()
440 spin_unlock_irqrestore(&s->lock, flags); in sidtab_convert()
445 params->target->count = count; in sidtab_convert()
448 s->convert = params; in sidtab_convert()
451 spin_unlock_irqrestore(&s->lock, flags); in sidtab_convert()
457 rc = sidtab_convert_tree(¶ms->target->roots[level], in sidtab_convert()
458 &s->roots[level], &pos, count, level, params); in sidtab_convert()
460 /* we need to keep the old table - disable live convert */ in sidtab_convert()
461 spin_lock_irqsave(&s->lock, flags); in sidtab_convert()
462 s->convert = NULL; in sidtab_convert()
463 spin_unlock_irqrestore(&s->lock, flags); in sidtab_convert()
468 * so we must re-acquire the lock here. in sidtab_convert()
470 spin_lock_irqsave(&s->lock, flags); in sidtab_convert()
471 sidtab_convert_hashtable(params->target, count); in sidtab_convert()
472 spin_unlock_irqrestore(&s->lock, flags); in sidtab_convert()
481 /* cancelling policy load - disable live convert of sidtab */ in sidtab_cancel_convert()
482 spin_lock_irqsave(&s->lock, flags); in sidtab_cancel_convert()
483 s->convert = NULL; in sidtab_cancel_convert()
484 spin_unlock_irqrestore(&s->lock, flags); in sidtab_cancel_convert()
487 void sidtab_freeze_begin(struct sidtab *s, unsigned long *flags) __acquires(&s->lock) in sidtab_freeze_begin()
489 spin_lock_irqsave(&s->lock, *flags); in sidtab_freeze_begin()
490 s->frozen = true; in sidtab_freeze_begin()
491 s->convert = NULL; in sidtab_freeze_begin()
493 void sidtab_freeze_end(struct sidtab *s, unsigned long *flags) __releases(&s->lock) in sidtab_freeze_end()
495 spin_unlock_irqrestore(&s->lock, *flags); in sidtab_freeze_end()
500 context_destroy(&entry->context); in sidtab_destroy_entry()
502 kfree(rcu_dereference_raw(entry->cache)); in sidtab_destroy_entry()
506 static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level) in sidtab_destroy_tree() argument
510 if (level != 0) { in sidtab_destroy_tree()
517 sidtab_destroy_tree(node->entries[i], level - 1); in sidtab_destroy_tree()
526 sidtab_destroy_entry(&node->entries[i]); in sidtab_destroy_tree()
533 u32 i, level; in sidtab_destroy() local
536 if (s->isids[i].set) in sidtab_destroy()
537 sidtab_destroy_entry(&s->isids[i].entry); in sidtab_destroy()
539 level = SIDTAB_MAX_LEVEL; in sidtab_destroy()
540 while (level && !s->roots[level].ptr_inner) in sidtab_destroy()
541 --level; in sidtab_destroy()
543 sidtab_destroy_tree(s->roots[level], level); in sidtab_destroy()
556 struct sidtab_str_cache *cache, *victim = NULL; in sidtab_sid2str_put() local
559 /* do not cache invalid contexts */ in sidtab_sid2str_put()
560 if (entry->context.len) in sidtab_sid2str_put()
563 spin_lock_irqsave(&s->cache_lock, flags); in sidtab_sid2str_put()
565 cache = rcu_dereference_protected(entry->cache, in sidtab_sid2str_put()
566 lockdep_is_held(&s->cache_lock)); in sidtab_sid2str_put()
567 if (cache) { in sidtab_sid2str_put()
568 /* entry in cache - just bump to the head of LRU list */ in sidtab_sid2str_put()
569 list_move(&cache->lru_member, &s->cache_lru_list); in sidtab_sid2str_put()
573 cache = kmalloc(sizeof(struct sidtab_str_cache) + str_len, GFP_ATOMIC); in sidtab_sid2str_put()
574 if (!cache) in sidtab_sid2str_put()
577 if (s->cache_free_slots == 0) { in sidtab_sid2str_put()
578 /* pop a cache entry from the tail and free it */ in sidtab_sid2str_put()
579 victim = container_of(s->cache_lru_list.prev, in sidtab_sid2str_put()
581 list_del(&victim->lru_member); in sidtab_sid2str_put()
582 rcu_assign_pointer(victim->parent->cache, NULL); in sidtab_sid2str_put()
584 s->cache_free_slots--; in sidtab_sid2str_put()
586 cache->parent = entry; in sidtab_sid2str_put()
587 cache->len = str_len; in sidtab_sid2str_put()
588 memcpy(cache->str, str, str_len); in sidtab_sid2str_put()
589 list_add(&cache->lru_member, &s->cache_lru_list); in sidtab_sid2str_put()
591 rcu_assign_pointer(entry->cache, cache); in sidtab_sid2str_put()
594 spin_unlock_irqrestore(&s->cache_lock, flags); in sidtab_sid2str_put()
601 struct sidtab_str_cache *cache; in sidtab_sid2str_get() local
604 if (entry->context.len) in sidtab_sid2str_get()
605 return -ENOENT; /* do not cache invalid contexts */ in sidtab_sid2str_get()
609 cache = rcu_dereference(entry->cache); in sidtab_sid2str_get()
610 if (!cache) { in sidtab_sid2str_get()
611 rc = -ENOENT; in sidtab_sid2str_get()
613 *out_len = cache->len; in sidtab_sid2str_get()
615 *out = kmemdup(cache->str, cache->len, GFP_ATOMIC); in sidtab_sid2str_get()
617 rc = -ENOMEM; in sidtab_sid2str_get()