From ee1a84fdfeedfd7362e9a8a8f15fedc3482ade2d Mon Sep 17 00:00:00 2001 From: Ondrej Mosnacek Date: Fri, 30 Nov 2018 16:24:08 +0100 Subject: selinux: overhaul sidtab to fix bug and improve performance Before this patch, during a policy reload the sidtab would become frozen and trying to map a new context to SID would be unable to add a new entry to sidtab and fail with -ENOMEM. Such failures are usually propagated into userspace, which has no way of distignuishing them from actual allocation failures and thus doesn't handle them gracefully. Such situation can be triggered e.g. by the following reproducer: while true; do load_policy; echo -n .; sleep 0.1; done & for (( i = 0; i < 1024; i++ )); do runcon -l s0:c$i echo -n x || break # or: # chcon -l s0:c$i || break done This patch overhauls the sidtab so it doesn't need to be frozen during policy reload, thus solving the above problem. The new SID table leverages the fact that SIDs are allocated sequentially and are never invalidated and stores them in linear buckets indexed by a tree structure. This brings several advantages: 1. Fast SID -> context lookup - this lookup can now be done in logarithmic time complexity (usually in less than 4 array lookups) and can still be done safely without locking. 2. No need to re-search the whole table on reverse lookup miss - after acquiring the spinlock only the newly added entries need to be searched, which means that reverse lookups that end up inserting a new entry are now about twice as fast. 3. No need to freeze sidtab during policy reload - it is now possible to handle insertion of new entries even during sidtab conversion. The tree structure of the new sidtab is able to grow automatically to up to about 2^31 entries (at which point it should not have more than about 4 tree levels). The old sidtab had a theoretical capacity of almost 2^32 entries, but half of that is still more than enough since by that point the reverse table lookups would become unusably slow anyway... The number of entries per tree node is selected automatically so that each node fits into a single page, which should be the easiest size for kmalloc() to handle. Note that the cache for reverse lookup is preserved with equivalent logic. The only difference is that instead of storing pointers to the hash table nodes it stores just the indices of the cached entries. The new cache ensures that the indices are loaded/stored atomically, but it still has the drawback that concurrent cache updates may mess up the contents of the cache. Such situation however only reduces its effectivity, not the correctness of lookups. Tested by selinux-testsuite and thoroughly tortured by this simple stress test: ``` function rand_cat() { echo $(( $RANDOM % 1024 )) } function do_work() { while true; do echo -n "system_u:system_r:kernel_t:s0:c$(rand_cat),c$(rand_cat)" \ >/sys/fs/selinux/context 2>/dev/null || true done } do_work >/dev/null & do_work >/dev/null & do_work >/dev/null & while load_policy; do echo -n .; sleep 0.1; done kill %1 kill %2 kill %3 ``` Link: https://github.com/SELinuxProject/selinux-kernel/issues/38 Reported-by: Orion Poplawski Reported-by: Li Kun Signed-off-by: Ondrej Mosnacek Reviewed-by: Stephen Smalley [PM: most of sidtab.c merged by hand due to conflicts] [PM: checkpatch fixes in mls.c, services.c, sidtab.c] Signed-off-by: Paul Moore --- security/selinux/ss/services.c | 122 +++++++++++++++++------------------------ 1 file changed, 51 insertions(+), 71 deletions(-) (limited to 'security/selinux/ss/services.c') diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c index 4ff4b0edbf6b..dd44126c8d14 100644 --- a/security/selinux/ss/services.c +++ b/security/selinux/ss/services.c @@ -1907,19 +1907,16 @@ struct convert_context_args { /* * Convert the values in the security context - * structure `c' from the values specified + * structure `oldc' from the values specified * in the policy `p->oldp' to the values specified - * in the policy `p->newp'. Verify that the - * context is valid under the new policy. + * in the policy `p->newp', storing the new context + * in `newc'. Verify that the context is valid + * under the new policy. */ -static int convert_context(u32 key, - struct context *c, - void *p) +static int convert_context(struct context *oldc, struct context *newc, void *p) { struct convert_context_args *args; - struct context oldc; struct ocontext *oc; - struct mls_range *range; struct role_datum *role; struct type_datum *typdatum; struct user_datum *usrdatum; @@ -1929,76 +1926,65 @@ static int convert_context(u32 key, args = p; - if (c->str) { - struct context ctx; - - rc = -ENOMEM; - s = kstrdup(c->str, GFP_KERNEL); + if (oldc->str) { + s = kstrdup(oldc->str, GFP_KERNEL); if (!s) - goto out; + return -ENOMEM; rc = string_to_context_struct(args->newp, NULL, s, - &ctx, SECSID_NULL); - kfree(s); - if (!rc) { - pr_info("SELinux: Context %s became valid (mapped).\n", - c->str); - /* Replace string with mapped representation. */ - kfree(c->str); - memcpy(c, &ctx, sizeof(*c)); - goto out; - } else if (rc == -EINVAL) { + newc, SECSID_NULL); + if (rc == -EINVAL) { /* Retain string representation for later mapping. */ - rc = 0; - goto out; - } else { + context_init(newc); + newc->str = s; + newc->len = oldc->len; + return 0; + } + kfree(s); + if (rc) { /* Other error condition, e.g. ENOMEM. */ pr_err("SELinux: Unable to map context %s, rc = %d.\n", - c->str, -rc); - goto out; + oldc->str, -rc); + return rc; } + pr_info("SELinux: Context %s became valid (mapped).\n", + oldc->str); + return 0; } - rc = context_cpy(&oldc, c); - if (rc) - goto out; + context_init(newc); /* Convert the user. */ rc = -EINVAL; usrdatum = hashtab_search(args->newp->p_users.table, - sym_name(args->oldp, SYM_USERS, c->user - 1)); + sym_name(args->oldp, + SYM_USERS, oldc->user - 1)); if (!usrdatum) goto bad; - c->user = usrdatum->value; + newc->user = usrdatum->value; /* Convert the role. */ rc = -EINVAL; role = hashtab_search(args->newp->p_roles.table, - sym_name(args->oldp, SYM_ROLES, c->role - 1)); + sym_name(args->oldp, SYM_ROLES, oldc->role - 1)); if (!role) goto bad; - c->role = role->value; + newc->role = role->value; /* Convert the type. */ rc = -EINVAL; typdatum = hashtab_search(args->newp->p_types.table, - sym_name(args->oldp, SYM_TYPES, c->type - 1)); + sym_name(args->oldp, + SYM_TYPES, oldc->type - 1)); if (!typdatum) goto bad; - c->type = typdatum->value; + newc->type = typdatum->value; /* Convert the MLS fields if dealing with MLS policies */ if (args->oldp->mls_enabled && args->newp->mls_enabled) { - rc = mls_convert_context(args->oldp, args->newp, c); + rc = mls_convert_context(args->oldp, args->newp, oldc, newc); if (rc) goto bad; - } else if (args->oldp->mls_enabled && !args->newp->mls_enabled) { - /* - * Switching between MLS and non-MLS policy: - * free any storage used by the MLS fields in the - * context for all existing entries in the sidtab. - */ - mls_context_destroy(c); } else if (!args->oldp->mls_enabled && args->newp->mls_enabled) { /* * Switching between non-MLS and MLS policy: @@ -2016,38 +2002,30 @@ static int convert_context(u32 key, " the initial SIDs list\n"); goto bad; } - range = &oc->context[0].range; - rc = mls_range_set(c, range); + rc = mls_range_set(newc, &oc->context[0].range); if (rc) goto bad; } /* Check the validity of the new context. */ - if (!policydb_context_isvalid(args->newp, c)) { - rc = convert_context_handle_invalid_context(args->state, - &oldc); + if (!policydb_context_isvalid(args->newp, newc)) { + rc = convert_context_handle_invalid_context(args->state, oldc); if (rc) goto bad; } - context_destroy(&oldc); - - rc = 0; -out: - return rc; + return 0; bad: /* Map old representation to string and save it. */ - rc = context_struct_to_string(args->oldp, &oldc, &s, &len); + rc = context_struct_to_string(args->oldp, oldc, &s, &len); if (rc) return rc; - context_destroy(&oldc); - context_destroy(c); - c->str = s; - c->len = len; + context_destroy(newc); + newc->str = s; + newc->len = len; pr_info("SELinux: Context %s became invalid (unmapped).\n", - c->str); - rc = 0; - goto out; + newc->str); + return 0; } static void security_load_policycaps(struct selinux_state *state) @@ -2091,6 +2069,7 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len) struct policydb *oldpolicydb, *newpolicydb; struct selinux_mapping *oldmapping; struct selinux_map newmap; + struct sidtab_convert_params convert_params; struct convert_context_args args; u32 seqno; int rc = 0; @@ -2147,12 +2126,6 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len) goto out; } - oldsidtab = state->ss->sidtab; - -#if 0 - sidtab_hash_eval(oldsidtab, "sids"); -#endif - rc = policydb_read(newpolicydb, fp); if (rc) { kfree(newsidtab); @@ -2184,6 +2157,8 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len) goto err; } + oldsidtab = state->ss->sidtab; + /* * Convert the internal representations of contexts * in the new SID table. @@ -2191,7 +2166,12 @@ int security_load_policy(struct selinux_state *state, void *data, size_t len) args.state = state; args.oldp = policydb; args.newp = newpolicydb; - rc = sidtab_convert(oldsidtab, newsidtab, convert_context, &args); + + convert_params.func = convert_context; + convert_params.args = &args; + convert_params.target = newsidtab; + + rc = sidtab_convert(oldsidtab, &convert_params); if (rc) { pr_err("SELinux: unable to convert the internal" " representation of contexts in the new SID" -- cgit v1.2.3-59-g8ed1b