[linux-2.6-block.git] / security / selinux / ss / sidtab.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Implementation of the SID table type.
 *
 * Original author: Stephen Smalley, <stephen.smalley.work@gmail.com>
 * Author: Ondrej Mosnacek, <omosnacek@gmail.com>
 *
 * Copyright (C) 2018 Red Hat, Inc.
 */

#include <linux/errno.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/rcupdate.h>
#include <linux/slab.h>
#include <linux/sched.h>
#include <linux/spinlock.h>
#include <asm/barrier.h>
#include "flask.h"
#include "security.h"
#include "sidtab.h"
#include "services.h"

struct sidtab_str_cache {
	struct rcu_head rcu_member;
	struct list_head lru_member;
	struct sidtab_entry *parent;
	u32 len;
	char str[] __counted_by(len);
};

#define index_to_sid(index) ((index) + SECINITSID_NUM + 1)
#define sid_to_index(sid)   ((sid) - (SECINITSID_NUM + 1))

int sidtab_init(struct sidtab *s)
{
	u32 i;

	memset(s->roots, 0, sizeof(s->roots));

	for (i = 0; i < SECINITSID_NUM; i++)
		s->isids[i].set = 0;

	s->frozen = false;
	s->count = 0;
	s->convert = NULL;
	hash_init(s->context_to_sid);

	spin_lock_init(&s->lock);

#if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0
	s->cache_free_slots = CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE;
	INIT_LIST_HEAD(&s->cache_lru_list);
	spin_lock_init(&s->cache_lock);
#endif

	return 0;
}

static u32 context_to_sid(struct sidtab *s, struct context *context, u32 hash)
{
	struct sidtab_entry *entry;
	u32 sid = 0;

	rcu_read_lock();
	hash_for_each_possible_rcu(s->context_to_sid, entry, list, hash) {
		if (entry->hash != hash)
			continue;
		if (context_cmp(&entry->context, context)) {
			sid = entry->sid;
			break;
		}
	}
	rcu_read_unlock();
	return sid;
}

int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
{
	struct sidtab_isid_entry *isid;
	u32 hash;
	int rc;

	if (sid == 0 || sid > SECINITSID_NUM)
		return -EINVAL;

	isid = &s->isids[sid - 1];

	rc = context_cpy(&isid->entry.context, context);
	if (rc)
		return rc;

#if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0
	isid->entry.cache = NULL;
#endif
	isid->set = 1;

	hash = context_compute_hash(context);

	/*
	 * Multiple initial sids may map to the same context. Check that this
	 * context is not already represented in the context_to_sid hashtable
	 * to avoid duplicate entries and long linked lists upon hash
	 * collision.
	 */
	if (!context_to_sid(s, context, hash)) {
		isid->entry.sid = sid;
		isid->entry.hash = hash;
		hash_add(s->context_to_sid, &isid->entry.list, hash);
	}

	return 0;
}

int sidtab_hash_stats(struct sidtab *sidtab, char *page)
{
	int i;
	int chain_len = 0;
	int slots_used = 0;
	int entries = 0;
	int max_chain_len = 0;
	int cur_bucket = 0;
	struct sidtab_entry *entry;

	rcu_read_lock();
	hash_for_each_rcu(sidtab->context_to_sid, i, entry, list) {
		entries++;
		if (i == cur_bucket) {
			chain_len++;
			if (chain_len == 1)
				slots_used++;
		} else {
			cur_bucket = i;
			if (chain_len > max_chain_len)
				max_chain_len = chain_len;
			chain_len = 0;
		}
	}
	rcu_read_unlock();

	if (chain_len > max_chain_len)
		max_chain_len = chain_len;

	return scnprintf(page, PAGE_SIZE,
			 "entries: %d\nbuckets used: %d/%d\n"
			 "longest chain: %d\n",
			 entries, slots_used, SIDTAB_HASH_BUCKETS,
			 max_chain_len);
}

static u32 sidtab_level_from_count(u32 count)
{
	u32 capacity = SIDTAB_LEAF_ENTRIES;
	u32 level = 0;

	while (count > capacity) {
		capacity <<= SIDTAB_INNER_SHIFT;
		++level;
	}
	return level;
}

static int sidtab_alloc_roots(struct sidtab *s, u32 level)
{
	u32 l;

	if (!s->roots[0].ptr_leaf) {
		s->roots[0].ptr_leaf =
			kzalloc(SIDTAB_NODE_ALLOC_SIZE, GFP_ATOMIC);
		if (!s->roots[0].ptr_leaf)
			return -ENOMEM;
	}
	for (l = 1; l <= level; ++l)
		if (!s->roots[l].ptr_inner) {
			s->roots[l].ptr_inner =
				kzalloc(SIDTAB_NODE_ALLOC_SIZE, GFP_ATOMIC);
			if (!s->roots[l].ptr_inner)
				return -ENOMEM;
			s->roots[l].ptr_inner->entries[0] = s->roots[l - 1];
		}
	return 0;
}

static struct sidtab_entry *sidtab_do_lookup(struct sidtab *s, u32 index,
					     int alloc)
{
	union sidtab_entry_inner *entry;
	u32 level, capacity_shift, leaf_index = index / SIDTAB_LEAF_ENTRIES;

	/* find the level of the subtree we need */
	level = sidtab_level_from_count(index + 1);
	capacity_shift = level * SIDTAB_INNER_SHIFT;

	/* allocate roots if needed */
	if (alloc && sidtab_alloc_roots(s, level) != 0)
		return NULL;

	/* lookup inside the subtree */
	entry = &s->roots[level];
	while (level != 0) {
		capacity_shift -= SIDTAB_INNER_SHIFT;
		--level;

		entry = &entry->ptr_inner->entries[leaf_index >> capacity_shift];
		leaf_index &= ((u32)1 << capacity_shift) - 1;

		if (!entry->ptr_inner) {
			if (alloc)
				entry->ptr_inner = kzalloc(
					SIDTAB_NODE_ALLOC_SIZE, GFP_ATOMIC);
			if (!entry->ptr_inner)
				return NULL;
		}
	}
	if (!entry->ptr_leaf) {
		if (alloc)
			entry->ptr_leaf =
				kzalloc(SIDTAB_NODE_ALLOC_SIZE, GFP_ATOMIC);
		if (!entry->ptr_leaf)
			return NULL;
	}
	return &entry->ptr_leaf->entries[index % SIDTAB_LEAF_ENTRIES];
}

static struct sidtab_entry *sidtab_lookup(struct sidtab *s, u32 index)
{
	/* read entries only after reading count */
	u32 count = smp_load_acquire(&s->count);

	if (index >= count)
		return NULL;

	return sidtab_do_lookup(s, index, 0);
}

static struct sidtab_entry *sidtab_lookup_initial(struct sidtab *s, u32 sid)
{
	return s->isids[sid - 1].set ? &s->isids[sid - 1].entry : NULL;
}

static struct sidtab_entry *sidtab_search_core(struct sidtab *s, u32 sid,
					       int force)
{
	if (sid != 0) {
		struct sidtab_entry *entry;

		if (sid > SECINITSID_NUM)
			entry = sidtab_lookup(s, sid_to_index(sid));
		else
			entry = sidtab_lookup_initial(s, sid);
		if (entry && (!entry->context.len || force))
			return entry;
	}

	return sidtab_lookup_initial(s, SECINITSID_UNLABELED);
}

struct sidtab_entry *sidtab_search_entry(struct sidtab *s, u32 sid)
{
	return sidtab_search_core(s, sid, 0);
}

struct sidtab_entry *sidtab_search_entry_force(struct sidtab *s, u32 sid)
{
	return sidtab_search_core(s, sid, 1);
}

int sidtab_context_to_sid(struct sidtab *s, struct context *context, u32 *sid)
{
	unsigned long flags;
	u32 count, hash = context_compute_hash(context);
	struct sidtab_convert_params *convert;
	struct sidtab_entry *dst, *dst_convert;
	int rc;

	*sid = context_to_sid(s, context, hash);
	if (*sid)
		return 0;

	/* lock-free search failed: lock, re-search, and insert if not found */
	spin_lock_irqsave(&s->lock, flags);

	rc = 0;
	*sid = context_to_sid(s, context, hash);
	if (*sid)
		goto out_unlock;

	if (unlikely(s->frozen)) {
		/*
		 * This sidtab is now frozen - tell the caller to abort and
		 * get the new one.
		 */
		rc = -ESTALE;
		goto out_unlock;
	}

	count = s->count;

	/* bail out if we already reached max entries */
	rc = -EOVERFLOW;
	if (count >= SIDTAB_MAX)
		goto out_unlock;

	/* insert context into new entry */
	rc = -ENOMEM;
	dst = sidtab_do_lookup(s, count, 1);
	if (!dst)
		goto out_unlock;

	dst->sid = index_to_sid(count);
	dst->hash = hash;

	rc = context_cpy(&dst->context, context);
	if (rc)
		goto out_unlock;

	/*
	 * if we are building a new sidtab, we need to convert the context
	 * and insert it there as well
	 */
	convert = s->convert;
	if (convert) {
		struct sidtab *target = convert->target;

		rc = -ENOMEM;
		dst_convert = sidtab_do_lookup(target, count, 1);
		if (!dst_convert) {
			context_destroy(&dst->context);
			goto out_unlock;
		}

		rc = services_convert_context(convert->args, context,
					      &dst_convert->context,
					      GFP_ATOMIC);
		if (rc) {
			context_destroy(&dst->context);
			goto out_unlock;
		}
		dst_convert->sid = index_to_sid(count);
		dst_convert->hash = context_compute_hash(&dst_convert->context);
		target->count = count + 1;

		hash_add_rcu(target->context_to_sid, &dst_convert->list,
			     dst_convert->hash);
	}

	if (context->len)
		pr_info("SELinux:  Context %s is not valid (left unmapped).\n",
			context->str);

	*sid = index_to_sid(count);

	/* write entries before updating count */
	smp_store_release(&s->count, count + 1);
	hash_add_rcu(s->context_to_sid, &dst->list, dst->hash);

	rc = 0;
out_unlock:
	spin_unlock_irqrestore(&s->lock, flags);
	return rc;
}

static void sidtab_convert_hashtable(struct sidtab *s, u32 count)
{
	struct sidtab_entry *entry;
	u32 i;

	for (i = 0; i < count; i++) {
		entry = sidtab_do_lookup(s, i, 0);
		entry->sid = index_to_sid(i);
		entry->hash = context_compute_hash(&entry->context);

		hash_add_rcu(s->context_to_sid, &entry->list, entry->hash);
	}
}

static int sidtab_convert_tree(union sidtab_entry_inner *edst,
			       union sidtab_entry_inner *esrc, u32 *pos,
			       u32 count, u32 level,
			       struct sidtab_convert_params *convert)
{
	int rc;
	u32 i;

	if (level != 0) {
		if (!edst->ptr_inner) {
			edst->ptr_inner =
				kzalloc(SIDTAB_NODE_ALLOC_SIZE, GFP_KERNEL);
			if (!edst->ptr_inner)
				return -ENOMEM;
		}
		i = 0;
		while (i < SIDTAB_INNER_ENTRIES && *pos < count) {
			rc = sidtab_convert_tree(&edst->ptr_inner->entries[i],
						 &esrc->ptr_inner->entries[i],
						 pos, count, level - 1,
						 convert);
			if (rc)
				return rc;
			i++;
		}
	} else {
		if (!edst->ptr_leaf) {
			edst->ptr_leaf =
				kzalloc(SIDTAB_NODE_ALLOC_SIZE, GFP_KERNEL);
			if (!edst->ptr_leaf)
				return -ENOMEM;
		}
		i = 0;
		while (i < SIDTAB_LEAF_ENTRIES && *pos < count) {
			rc = services_convert_context(
				convert->args,
				&esrc->ptr_leaf->entries[i].context,
				&edst->ptr_leaf->entries[i].context,
				GFP_KERNEL);
			if (rc)
				return rc;
			(*pos)++;
			i++;
		}
		cond_resched();
	}
	return 0;
}

int sidtab_convert(struct sidtab *s, struct sidtab_convert_params *params)
{
	unsigned long flags;
	u32 count, level, pos;
	int rc;

	spin_lock_irqsave(&s->lock, flags);

	/* concurrent policy loads are not allowed */
	if (s->convert) {
		spin_unlock_irqrestore(&s->lock, flags);
		return -EBUSY;
	}

	count = s->count;
	level = sidtab_level_from_count(count);

	/* allocate last leaf in the new sidtab (to avoid race with
	 * live convert)
	 */
	rc = sidtab_do_lookup(params->target, count - 1, 1) ? 0 : -ENOMEM;
	if (rc) {
		spin_unlock_irqrestore(&s->lock, flags);
		return rc;
	}

	/* set count in case no new entries are added during conversion */
	params->target->count = count;

	/* enable live convert of new entries */
	s->convert = params;

	/* we can safely convert the tree outside the lock */
	spin_unlock_irqrestore(&s->lock, flags);

	pr_info("SELinux:  Converting %u SID table entries...\n", count);

	/* convert all entries not covered by live convert */
	pos = 0;
	rc = sidtab_convert_tree(&params->target->roots[level],
				 &s->roots[level], &pos, count, level, params);
	if (rc) {
		/* we need to keep the old table - disable live convert */
		spin_lock_irqsave(&s->lock, flags);
		s->convert = NULL;
		spin_unlock_irqrestore(&s->lock, flags);
		return rc;
	}
	/*
	 * The hashtable can also be modified in sidtab_context_to_sid()
	 * so we must re-acquire the lock here.
	 */
	spin_lock_irqsave(&s->lock, flags);
	sidtab_convert_hashtable(params->target, count);
	spin_unlock_irqrestore(&s->lock, flags);

	return 0;
}

void sidtab_cancel_convert(struct sidtab *s)
{
	unsigned long flags;

	/* cancelling policy load - disable live convert of sidtab */
	spin_lock_irqsave(&s->lock, flags);
	s->convert = NULL;
	spin_unlock_irqrestore(&s->lock, flags);
}

void sidtab_freeze_begin(struct sidtab *s, unsigned long *flags)
	__acquires(&s->lock)
{
	spin_lock_irqsave(&s->lock, *flags);
	s->frozen = true;
	s->convert = NULL;
}
void sidtab_freeze_end(struct sidtab *s, unsigned long *flags)
	__releases(&s->lock)
{
	spin_unlock_irqrestore(&s->lock, *flags);
}

static void sidtab_destroy_entry(struct sidtab_entry *entry)
{
	context_destroy(&entry->context);
#if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0
	kfree(rcu_dereference_raw(entry->cache));
#endif
}

static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level)
{
	u32 i;

	if (level != 0) {
		struct sidtab_node_inner *node = entry.ptr_inner;

		if (!node)
			return;

		for (i = 0; i < SIDTAB_INNER_ENTRIES; i++)
			sidtab_destroy_tree(node->entries[i], level - 1);
		kfree(node);
	} else {
		struct sidtab_node_leaf *node = entry.ptr_leaf;

		if (!node)
			return;

		for (i = 0; i < SIDTAB_LEAF_ENTRIES; i++)
			sidtab_destroy_entry(&node->entries[i]);
		kfree(node);
	}
}

void sidtab_destroy(struct sidtab *s)
{
	u32 i, level;

	for (i = 0; i < SECINITSID_NUM; i++)
		if (s->isids[i].set)
			sidtab_destroy_entry(&s->isids[i].entry);

	level = SIDTAB_MAX_LEVEL;
	while (level && !s->roots[level].ptr_inner)
		--level;

	sidtab_destroy_tree(s->roots[level], level);
	/*
	 * The context_to_sid hashtable's objects are all shared
	 * with the isids array and context tree, and so don't need
	 * to be cleaned up here.
	 */
}

#if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0

void sidtab_sid2str_put(struct sidtab *s, struct sidtab_entry *entry,
			const char *str, u32 str_len)
{
	struct sidtab_str_cache *cache, *victim = NULL;
	unsigned long flags;

	/* do not cache invalid contexts */
	if (entry->context.len)
		return;

	spin_lock_irqsave(&s->cache_lock, flags);

	cache = rcu_dereference_protected(entry->cache,
					  lockdep_is_held(&s->cache_lock));
	if (cache) {
		/* entry in cache - just bump to the head of LRU list */
		list_move(&cache->lru_member, &s->cache_lru_list);
		goto out_unlock;
	}

	cache = kmalloc(struct_size(cache, str, str_len), GFP_ATOMIC);
	if (!cache)
		goto out_unlock;

	if (s->cache_free_slots == 0) {
		/* pop a cache entry from the tail and free it */
		victim = container_of(s->cache_lru_list.prev,
				      struct sidtab_str_cache, lru_member);
		list_del(&victim->lru_member);
		rcu_assign_pointer(victim->parent->cache, NULL);
	} else {
		s->cache_free_slots--;
	}
	cache->parent = entry;
	cache->len = str_len;
	memcpy(cache->str, str, str_len);
	list_add(&cache->lru_member, &s->cache_lru_list);

	rcu_assign_pointer(entry->cache, cache);

out_unlock:
	spin_unlock_irqrestore(&s->cache_lock, flags);
	kfree_rcu(victim, rcu_member);
}

int sidtab_sid2str_get(struct sidtab *s, struct sidtab_entry *entry, char **out,
		       u32 *out_len)
{
	struct sidtab_str_cache *cache;
	int rc = 0;

	if (entry->context.len)
		return -ENOENT; /* do not cache invalid contexts */

	rcu_read_lock();

	cache = rcu_dereference(entry->cache);
	if (!cache) {
		rc = -ENOENT;
	} else {
		*out_len = cache->len;
		if (out) {
			*out = kmemdup(cache->str, cache->len, GFP_ATOMIC);
			if (!*out)
				rc = -ENOMEM;
		}
	}

	rcu_read_unlock();

	if (!rc && out)
		sidtab_sid2str_put(s, entry, *out, *out_len);
	return rc;
}

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