Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Stephen Smalley <sds@tycho.nsa.gov>]

On 1/16/20 4:39 PM, Lucas Stach wrote:
> The current hash is too small for current usages in, e.g. the Fedora standard
> policy. On file creates a considerable amount of CPU time is spent walking the
> the hash chains. Increasing the number of hash buckets somewhat mitigates the
> issue, but doesn't completely get rid of the long hash chains.
> 
> This patch does take the bit more invasive route by converting the filename
> trans hash to a rhashtable to allow this hash to scale with load.
> 
> fs_mark create benchmark on a SSD device, no ramdisk:
> Count          Size       Files/sec     App Overhead
> before:
> 10000          512        512.3           147715
> after:
> 10000          512        572.3            75141
> 
> filenametr_cmp(), which was the topmost function in the CPU cycle trace before
> at ~5% of the overall CPU time, is now down in the noise.

Thank you for working on this.  IMHO, Fedora overuses name-based type 
transitions but that's another topic. I haven't yet investigated the 
root cause but with your patch applied, I see some test failures related 
to name-based transitions:

[...]
#   Failed test at overlay/test line 439.
overlay/test ................ 114/119 # Looks like you failed 1 test of 119.
[...]
filesystem/test ............. 3/70 File context error, expected:
	test_filesystem_filenametranscon1_t
got:
	test_filesystem_filetranscon_t

#   Failed test at filesystem/test line 279.
File context error, expected:
	test_filesystem_filenametranscon2_t
got:
	test_filesystem_filetranscon_t

#   Failed test at filesystem/test line 286.
filesystem/test ............. 68/70 # Looks like you failed 2 tests of 70.

You can reproduce by cloning the selinux-testsuite from 
https://github.com/SELinuxProject/selinux-testsuite, applying the 
filesystem tests patch from
https://patchwork.kernel.org/patch/11337659/,
and following the README.md instructions.

> 
> Signed-off-by: Lucas Stach <dev@lynxeye.de>
> ---
>   security/selinux/ss/policydb.c | 140 +++++++++++++++++++++++----------
>   security/selinux/ss/policydb.h |  14 ++--
>   security/selinux/ss/services.c |  31 +-------
>   3 files changed, 109 insertions(+), 76 deletions(-)
> 
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index e20624a68f5d..d059317c15b6 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -34,6 +34,7 @@
>   #include <linux/string.h>
>   #include <linux/errno.h>
>   #include <linux/audit.h>
> +#include <linux/rhashtable.h>
>   #include "security.h"
>   
>   #include "policydb.h"
> @@ -334,15 +335,13 @@ static int (*destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) =
>   	cat_destroy,
>   };
>   
> -static int filenametr_destroy(void *key, void *datum, void *p)
> +static void filenametr_destroy(void *ptr, void *arg)
>   {
> -	struct filename_trans *ft = key;
> +	struct filename_trans *ft = ptr;
>   
>   	kfree(ft->name);
> -	kfree(key);
> -	kfree(datum);
> +	kfree(ft);
>   	cond_resched();
> -	return 0;
>   }
>   
>   static int range_tr_destroy(void *key, void *datum, void *p)
> @@ -404,9 +403,9 @@ static int roles_init(struct policydb *p)
>   	return rc;
>   }
>   
> -static u32 filenametr_hash(struct hashtab *h, const void *k)
> +static u32 filenametr_hash(const void *data, u32 len, u32 seed)
>   {
> -	const struct filename_trans *ft = k;
> +	const struct filename_trans *ft = data;
>   	unsigned long hash;
>   	unsigned int byte_num;
>   	unsigned char focus;
> @@ -416,13 +415,15 @@ static u32 filenametr_hash(struct hashtab *h, const void *k)
>   	byte_num = 0;
>   	while ((focus = ft->name[byte_num++]))
>   		hash = partial_name_hash(focus, hash);
> -	return hash & (h->size - 1);
> +
> +	return end_name_hash(hash);
>   }
>   
> -static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
> +static int filenametr_cmp(struct rhashtable_compare_arg *arg,
> +			  const void *obj)
>   {
> -	const struct filename_trans *ft1 = k1;
> -	const struct filename_trans *ft2 = k2;
> +	const struct filename_trans *ft1 = arg->key;
> +	const struct filename_trans *ft2 = obj;
>   	int v;
>   
>   	v = ft1->stype - ft2->stype;
> @@ -441,6 +442,39 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
>   
>   }
>   
> +static const struct rhashtable_params filename_trans_hashparams = {
> +	.nelem_hint		= 1024,
> +	.head_offset		= offsetof(struct filename_trans, hash_head),
> +	.obj_hashfn		= filenametr_hash,
> +	.obj_cmpfn		= filenametr_cmp,
> +};
> +
> +void policydb_filename_compute_type(struct policydb *policydb,
> +				    struct context *newcontext,
> +				    u32 stype, u32 ttype, u16 tclass,
> +				    const char *objname)
> +{
> +	struct filename_trans key, *ft;
> +
> +	/*
> +	 * Most filename trans rules are going to live in specific directories
> +	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
> +	 * if the ttype does not contain any rules.
> +	 */
> +	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> +		return;
> +
> +	key.stype = stype;
> +	key.ttype = ttype;
> +	key.tclass = tclass;
> +	key.name = objname;
> +
> +	ft = rhashtable_lookup(&policydb->filename_trans, &key,
> +			       filename_trans_hashparams);
> +	if (ft)
> +		newcontext->type = ft->otype;
> +}
> +
>   static u32 rangetr_hash(struct hashtab *h, const void *k)
>   {
>   	const struct range_trans *key = k;
> @@ -494,12 +528,7 @@ static int policydb_init(struct policydb *p)
>   	if (rc)
>   		goto out;
>   
> -	p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
> -					   (1 << 10));
> -	if (!p->filename_trans) {
> -		rc = -ENOMEM;
> -		goto out;
> -	}
> +	rhashtable_init(&p->filename_trans, &filename_trans_hashparams);
>   
>   	p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256);
>   	if (!p->range_tr) {
> @@ -513,7 +542,7 @@ static int policydb_init(struct policydb *p)
>   
>   	return 0;
>   out:
> -	hashtab_destroy(p->filename_trans);
> +	rhashtable_destroy(&p->filename_trans);
>   	hashtab_destroy(p->range_tr);
>   	for (i = 0; i < SYM_NUM; i++) {
>   		hashtab_map(p->symtab[i].table, destroy_f[i], NULL);
> @@ -831,8 +860,8 @@ void policydb_destroy(struct policydb *p)
>   	}
>   	kfree(lra);
>   
> -	hashtab_map(p->filename_trans, filenametr_destroy, NULL);
> -	hashtab_destroy(p->filename_trans);
> +	rhashtable_free_and_destroy(&p->filename_trans, filenametr_destroy,
> +				    NULL);
>   
>   	hashtab_map(p->range_tr, range_tr_destroy, NULL);
>   	hashtab_destroy(p->range_tr);
> @@ -1878,7 +1907,6 @@ static int range_read(struct policydb *p, void *fp)
>   static int filename_trans_read(struct policydb *p, void *fp)
>   {
>   	struct filename_trans *ft;
> -	struct filename_trans_datum *otype;
>   	char *name;
>   	u32 nel, len;
>   	__le32 buf[4];
> @@ -1893,7 +1921,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   	nel = le32_to_cpu(buf[0]);
>   
>   	for (i = 0; i < nel; i++) {
> -		otype = NULL;
>   		name = NULL;
>   
>   		rc = -ENOMEM;
> @@ -1901,11 +1928,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   		if (!ft)
>   			goto out;
>   
> -		rc = -ENOMEM;
> -		otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> -		if (!otype)
> -			goto out;
> -
>   		/* length of the path component string */
>   		rc = next_entry(buf, fp, sizeof(u32));
>   		if (rc)
> @@ -1926,14 +1948,14 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   		ft->stype = le32_to_cpu(buf[0]);
>   		ft->ttype = le32_to_cpu(buf[1]);
>   		ft->tclass = le32_to_cpu(buf[2]);
> -
> -		otype->otype = le32_to_cpu(buf[3]);
> +		ft->otype = le32_to_cpu(buf[3]);
>   
>   		rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
>   		if (rc)
>   			goto out;
>   
> -		rc = hashtab_insert(p->filename_trans, ft, otype);
> +		rc = rhashtable_insert_fast(&p->filename_trans, &ft->hash_head,
> +					    filename_trans_hashparams);
>   		if (rc) {
>   			/*
>   			 * Do not return -EEXIST to the caller, or the system
> @@ -1944,15 +1966,12 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   			/* But free memory to avoid memory leak. */
>   			kfree(ft);
>   			kfree(name);
> -			kfree(otype);
>   		}
>   	}
> -	hash_eval(p->filename_trans, "filenametr");
>   	return 0;
>   out:
>   	kfree(ft);
>   	kfree(name);
> -	kfree(otype);
>   
>   	return rc;
>   }
> @@ -3323,12 +3342,10 @@ static int range_write(struct policydb *p, void *fp)
>   	return 0;
>   }
>   
> -static int filename_write_helper(void *key, void *data, void *ptr)
> +static int filename_write_helper(struct filename_trans *ft,
> +				 struct policy_file *fp)
>   {
>   	__le32 buf[4];
> -	struct filename_trans *ft = key;
> -	struct filename_trans_datum *otype = data;
> -	void *fp = ptr;
>   	int rc;
>   	u32 len;
>   
> @@ -3345,7 +3362,7 @@ static int filename_write_helper(void *key, void *data, void *ptr)
>   	buf[0] = cpu_to_le32(ft->stype);
>   	buf[1] = cpu_to_le32(ft->ttype);
>   	buf[2] = cpu_to_le32(ft->tclass);
> -	buf[3] = cpu_to_le32(otype->otype);
> +	buf[3] = cpu_to_le32(ft->otype);
>   
>   	rc = put_entry(buf, sizeof(u32), 4, fp);
>   	if (rc)
> @@ -3356,15 +3373,34 @@ static int filename_write_helper(void *key, void *data, void *ptr)
>   
>   static int filename_trans_write(struct policydb *p, void *fp)
>   {
> -	u32 nel;
> +	u32 nel = 0;
>   	__le32 buf[1];
> -	int rc;
> +	int rc = 0;
> +	struct rhashtable_iter iter;
>   
>   	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
>   		return 0;
>   
> -	nel = 0;
> -	rc = hashtab_map(p->filename_trans, hashtab_cnt, &nel);
> +	rhashtable_walk_enter(&p->filename_trans, &iter);
> +	rhashtable_walk_start(&iter);
> +	for(;;) {
> +		struct filename_trans *trans;
> +
> +		trans = rhashtable_walk_next(&iter);
> +		if (!trans)
> +			break;
> +		if (IS_ERR(trans)) {
> +			if (PTR_ERR(trans) == -EAGAIN) {
> +				nel = 0;
> +				continue;
> +			}
> +			rc = PTR_ERR(trans);
> +			break;
> +		}
> +		nel++;
> +	};
> +	rhashtable_walk_stop(&iter);
> +	rhashtable_walk_exit(&iter);
>   	if (rc)
>   		return rc;
>   
> @@ -3373,7 +3409,25 @@ static int filename_trans_write(struct policydb *p, void *fp)
>   	if (rc)
>   		return rc;
>   
> -	rc = hashtab_map(p->filename_trans, filename_write_helper, fp);
> +	rhashtable_walk_enter(&p->filename_trans, &iter);
> +	rhashtable_walk_start(&iter);
> +	for(;;) {
> +		struct filename_trans *trans;
> +
> +		trans = rhashtable_walk_next(&iter);
> +		if (!trans)
> +			break;
> +		if (IS_ERR(trans)) {
> +			if (PTR_ERR(trans) == -EAGAIN) {
> +				continue;
> +			}
> +			rc = PTR_ERR(trans);
> +			break;
> +		}
> +		filename_write_helper(trans, fp);
> +	};
> +	rhashtable_walk_stop(&iter);
> +	rhashtable_walk_exit(&iter);
>   	if (rc)
>   		return rc;
>   
> diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> index bc56b14e2216..f1d2f5166af2 100644
> --- a/security/selinux/ss/policydb.h
> +++ b/security/selinux/ss/policydb.h
> @@ -29,6 +29,7 @@
>   #include "mls_types.h"
>   #include "context.h"
>   #include "constraint.h"
> +#include <linux/rhashtable.h>
>   
>   /*
>    * A datum type is defined for each kind of symbol
> @@ -90,16 +91,14 @@ struct role_trans {
>   };
>   
>   struct filename_trans {
> +	struct rhash_head hash_head;
> +	u32 otype;
>   	u32 stype;		/* current process */
>   	u32 ttype;		/* parent dir context */
>   	u16 tclass;		/* class of new object */
>   	const char *name;	/* last path component */
>   };
>   
> -struct filename_trans_datum {
> -	u32 otype;		/* expected of new object */
> -};
> -
>   struct role_allow {
>   	u32 role;		/* current role */
>   	u32 new_role;		/* new role */
> @@ -266,7 +265,7 @@ struct policydb {
>   	/* quickly exclude lookups when parent ttype has no rules */
>   	struct ebitmap filename_trans_ttypes;
>   	/* actual set of filename_trans rules */
> -	struct hashtab *filename_trans;
> +	struct rhashtable filename_trans;
>   
>   	/* bools indexed by (value - 1) */
>   	struct cond_bool_datum **bool_val_to_struct;
> @@ -318,6 +317,11 @@ extern int policydb_role_isvalid(struct policydb *p, unsigned int role);
>   extern int policydb_read(struct policydb *p, void *fp);
>   extern int policydb_write(struct policydb *p, void *fp);
>   
> +void policydb_filename_compute_type(struct policydb *policydb,
> +				    struct context *newcontext,
> +				    u32 stype, u32 ttype, u16 tclass,
> +				    const char *objname);
> +
>   #define PERM_SYMTAB_SIZE 32
>   
>   #define POLICYDB_CONFIG_MLS    1
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index a5813c7629c1..60a98d900dd3 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1607,32 +1607,6 @@ static int compute_sid_handle_invalid_context(
>   	return -EACCES;
>   }
>   
> -static void filename_compute_type(struct policydb *policydb,
> -				  struct context *newcontext,
> -				  u32 stype, u32 ttype, u16 tclass,
> -				  const char *objname)
> -{
> -	struct filename_trans ft;
> -	struct filename_trans_datum *otype;
> -
> -	/*
> -	 * Most filename trans rules are going to live in specific directories
> -	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
> -	 * if the ttype does not contain any rules.
> -	 */
> -	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> -		return;
> -
> -	ft.stype = stype;
> -	ft.ttype = ttype;
> -	ft.tclass = tclass;
> -	ft.name = objname;
> -
> -	otype = hashtab_search(policydb->filename_trans, &ft);
> -	if (otype)
> -		newcontext->type = otype->otype;
> -}
> -
>   static int security_compute_sid(struct selinux_state *state,
>   				u32 ssid,
>   				u32 tsid,
> @@ -1770,8 +1744,9 @@ static int security_compute_sid(struct selinux_state *state,
>   
>   	/* if we have a objname this is a file trans check so check those rules */
>   	if (objname)
> -		filename_compute_type(policydb, &newcontext, scontext->type,
> -				      tcontext->type, tclass, objname);
> +		policydb_filename_compute_type(policydb, &newcontext,
> +					       scontext->type, tcontext->type,
> +					       tclass, objname);
>   
>   	/* Check for class-specific changes. */
>   	if (specified & AVTAB_TRANSITION) {
>