Messages in this thread Patch in this message |  | | Subject | Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable | From | Stephen Smalley <> | Date | Fri, 17 Jan 2020 14:11:38 -0500 |
| |
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) { >
|  |