| Message ID | 20200226155452.301544-1-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [v3] selinux: reduce the use of hard-coded hash sizes | expand |
On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Instead allocate hash tables with just the right size based on the > actual number of elements (which is almost always known beforehand, we > just need to defer the hashtab allocation to the right time). The only > case when we don't know the size (with the current policy format) is the > new filename transitions hashtable. Here I just left the existing value. > > After this patch, the time to load Fedora policy on x86_64 decreases > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > from 750 ms to 122 ms. It is also likely that other operations are going > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > but I didn't try to quantify that. > > The memory usage of all hash table arrays increases from ~58 KB to > ~163 KB (with Fedora policy on x86_64). > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> Acked-by: Stephen Smalley <sds@tycho.nsa.gov>
On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Instead allocate hash tables with just the right size based on the > actual number of elements (which is almost always known beforehand, we > just need to defer the hashtab allocation to the right time). The only > case when we don't know the size (with the current policy format) is the > new filename transitions hashtable. Here I just left the existing value. > > After this patch, the time to load Fedora policy on x86_64 decreases > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > from 750 ms to 122 ms. It is also likely that other operations are going > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > but I didn't try to quantify that. > > The memory usage of all hash table arrays increases from ~58 KB to > ~163 KB (with Fedora policy on x86_64). > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > > Changed in v3: > - switch to simpler and more logical hash size heuristic > - add comment explaining the choice of the heuristic > > Changed in v2: > - guard against h->size == 0 in hashtab_search() and hashtab_insert() > > security/selinux/ss/hashtab.c | 28 +++++++++++++++--- > security/selinux/ss/hashtab.h | 2 +- > security/selinux/ss/policydb.c | 53 +++++++++++++--------------------- > security/selinux/ss/policydb.h | 2 -- > 4 files changed, 45 insertions(+), 40 deletions(-) Thanks Ondrej, this looks better; merged into selinux/next. Also, changing the hash heuristic in v3 really shrunk the memory usage compared to v2 without much impact on performance - a ~100k increase in memory is a small price to pay for the policy load improvement. Well done.
On Fri, Feb 28, 2020 at 1:27 AM Paul Moore <paul@paul-moore.com> wrote: > On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > Instead allocate hash tables with just the right size based on the > > actual number of elements (which is almost always known beforehand, we > > just need to defer the hashtab allocation to the right time). The only > > case when we don't know the size (with the current policy format) is the > > new filename transitions hashtable. Here I just left the existing value. > > > > After this patch, the time to load Fedora policy on x86_64 decreases > > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > > from 750 ms to 122 ms. It is also likely that other operations are going > > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > > but I didn't try to quantify that. > > > > The memory usage of all hash table arrays increases from ~58 KB to > > ~163 KB (with Fedora policy on x86_64). > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > --- > > > > Changed in v3: > > - switch to simpler and more logical hash size heuristic > > - add comment explaining the choice of the heuristic > > > > Changed in v2: > > - guard against h->size == 0 in hashtab_search() and hashtab_insert() > > > > security/selinux/ss/hashtab.c | 28 +++++++++++++++--- > > security/selinux/ss/hashtab.h | 2 +- > > security/selinux/ss/policydb.c | 53 +++++++++++++--------------------- > > security/selinux/ss/policydb.h | 2 -- > > 4 files changed, 45 insertions(+), 40 deletions(-) > > Thanks Ondrej, this looks better; merged into selinux/next. > > Also, changing the hash heuristic in v3 really shrunk the memory usage > compared to v2 without much impact on performance - a ~100k increase > in memory is a small price to pay for the policy load improvement. > Well done. Er... sorry, I forgot to document it clearly in the e-mails, but the usage didn't actually drop between the last two versions (it actually increased by ~36 KB). It's just that In the previous version I "measured" the memory usage just by looking at the total memory usage reported by top, which is however fluctuating a lot and I was apparently just measuring noise... For this patch I actually printk'd the sizes of the tables exactly (since that's the only thing this patch touches) and this showed these much smaller numbers. So please disregard the 1-2 MB from the previous patch versions - they were bogus.
On Fri, Feb 28, 2020 at 3:48 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > On Fri, Feb 28, 2020 at 1:27 AM Paul Moore <paul@paul-moore.com> wrote: > > On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > > > Instead allocate hash tables with just the right size based on the > > > actual number of elements (which is almost always known beforehand, we > > > just need to defer the hashtab allocation to the right time). The only > > > case when we don't know the size (with the current policy format) is the > > > new filename transitions hashtable. Here I just left the existing value. > > > > > > After this patch, the time to load Fedora policy on x86_64 decreases > > > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > > > from 750 ms to 122 ms. It is also likely that other operations are going > > > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > > > but I didn't try to quantify that. > > > > > > The memory usage of all hash table arrays increases from ~58 KB to > > > ~163 KB (with Fedora policy on x86_64). > > > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > > --- > > > > > > Changed in v3: > > > - switch to simpler and more logical hash size heuristic > > > - add comment explaining the choice of the heuristic > > > > > > Changed in v2: > > > - guard against h->size == 0 in hashtab_search() and hashtab_insert() > > > > > > security/selinux/ss/hashtab.c | 28 +++++++++++++++--- > > > security/selinux/ss/hashtab.h | 2 +- > > > security/selinux/ss/policydb.c | 53 +++++++++++++--------------------- > > > security/selinux/ss/policydb.h | 2 -- > > > 4 files changed, 45 insertions(+), 40 deletions(-) > > > > Thanks Ondrej, this looks better; merged into selinux/next. > > > > Also, changing the hash heuristic in v3 really shrunk the memory usage > > compared to v2 without much impact on performance - a ~100k increase > > in memory is a small price to pay for the policy load improvement. > > Well done. > > Er... sorry, I forgot to document it clearly in the e-mails, but the > usage didn't actually drop between the last two versions (it actually > increased by ~36 KB). It's just that In the previous version I > "measured" the memory usage just by looking at the total memory usage > reported by top, which is however fluctuating a lot and I was > apparently just measuring noise... For this patch I actually printk'd > the sizes of the tables exactly (since that's the only thing this > patch touches) and this showed these much smaller numbers. So please > disregard the 1-2 MB from the previous patch versions - they were > bogus. Okay, that makes a lot more sense now. I was a little shocked about the difference in memory usage (it honestly didn't make sense), but numbers don't typically lie so I figured I was just missing some small point which was having a big impact :) Regardless, a ~36KB bump in memory usage over the non-patched kernel is still a small price to pay for the performance increase.
On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Instead allocate hash tables with just the right size based on the > actual number of elements (which is almost always known beforehand, we > just need to defer the hashtab allocation to the right time). The only > case when we don't know the size (with the current policy format) is the > new filename transitions hashtable. Here I just left the existing value. > > After this patch, the time to load Fedora policy on x86_64 decreases > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > from 750 ms to 122 ms. It is also likely that other operations are going > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > but I didn't try to quantify that. > > The memory usage of all hash table arrays increases from ~58 KB to > ~163 KB (with Fedora policy on x86_64). > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > index 32b3a8acf96f..7ca8c74efba3 100644 > --- a/security/selinux/ss/policydb.c > +++ b/security/selinux/ss/policydb.c > @@ -503,20 +482,12 @@ static int policydb_init(struct policydb *p) > goto out; > } > > - p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256); > - if (!p->range_tr) { > - rc = -ENOMEM; > - goto out; > - } > - > ebitmap_init(&p->filename_trans_ttypes); > ebitmap_init(&p->policycaps); > ebitmap_init(&p->permissive_map); > > return 0; > out: > - hashtab_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); > hashtab_destroy(p->symtab[i].table); Sorry, just pointed out to me that this left the symtab destruction code in the out path of policydb_init() even though we are no longer creating them there. Harmless but should be dropped.
On Mon, Mar 2, 2020 at 2:11 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > Instead allocate hash tables with just the right size based on the > > actual number of elements (which is almost always known beforehand, we > > just need to defer the hashtab allocation to the right time). The only > > case when we don't know the size (with the current policy format) is the > > new filename transitions hashtable. Here I just left the existing value. > > > > After this patch, the time to load Fedora policy on x86_64 decreases > > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > > from 750 ms to 122 ms. It is also likely that other operations are going > > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > > but I didn't try to quantify that. > > > > The memory usage of all hash table arrays increases from ~58 KB to > > ~163 KB (with Fedora policy on x86_64). > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > --- > > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > > index 32b3a8acf96f..7ca8c74efba3 100644 > > --- a/security/selinux/ss/policydb.c > > +++ b/security/selinux/ss/policydb.c > > @@ -503,20 +482,12 @@ static int policydb_init(struct policydb *p) > > goto out; > > } > > > > - p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256); > > - if (!p->range_tr) { > > - rc = -ENOMEM; > > - goto out; > > - } > > - > > ebitmap_init(&p->filename_trans_ttypes); > > ebitmap_init(&p->policycaps); > > ebitmap_init(&p->permissive_map); > > > > return 0; > > out: > > - hashtab_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); > > hashtab_destroy(p->symtab[i].table); > > Sorry, just pointed out to me that this left the symtab destruction > code in the out path of policydb_init() > even though we are no longer creating them there. Harmless but should > be dropped. Ondrej, can you submit a cleanup patch for this?
On Tue, Mar 3, 2020 at 12:16 AM Paul Moore <paul@paul-moore.com> wrote: > On Mon, Mar 2, 2020 at 2:11 PM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > On Wed, Feb 26, 2020 at 10:55 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > > > Instead allocate hash tables with just the right size based on the > > > actual number of elements (which is almost always known beforehand, we > > > just need to defer the hashtab allocation to the right time). The only > > > case when we don't know the size (with the current policy format) is the > > > new filename transitions hashtable. Here I just left the existing value. > > > > > > After this patch, the time to load Fedora policy on x86_64 decreases > > > from 790 ms to 167 ms. If the unconfined module is removed, it decreases > > > from 750 ms to 122 ms. It is also likely that other operations are going > > > to be faster, mainly string_to_context_struct() or mls_compute_sid(), > > > but I didn't try to quantify that. > > > > > > The memory usage of all hash table arrays increases from ~58 KB to > > > ~163 KB (with Fedora policy on x86_64). > > > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > > --- > > > > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > > > index 32b3a8acf96f..7ca8c74efba3 100644 > > > --- a/security/selinux/ss/policydb.c > > > +++ b/security/selinux/ss/policydb.c > > > @@ -503,20 +482,12 @@ static int policydb_init(struct policydb *p) > > > goto out; > > > } > > > > > > - p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256); > > > - if (!p->range_tr) { > > > - rc = -ENOMEM; > > > - goto out; > > > - } > > > - > > > ebitmap_init(&p->filename_trans_ttypes); > > > ebitmap_init(&p->policycaps); > > > ebitmap_init(&p->permissive_map); > > > > > > return 0; > > > out: > > > - hashtab_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); > > > hashtab_destroy(p->symtab[i].table); > > > > Sorry, just pointed out to me that this left the symtab destruction > > code in the out path of policydb_init() > > even though we are no longer creating them there. Harmless but should > > be dropped. > > Ondrej, can you submit a cleanup patch for this? Sure, already on it... -- Ondrej Mosnacek <omosnace at redhat dot com> Software Engineer, Security Technologies Red Hat, Inc.
diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c index ebfdaa31ee32..883f19d32c28 100644 --- a/security/selinux/ss/hashtab.c +++ b/security/selinux/ss/hashtab.c @@ -12,12 +12,29 @@ static struct kmem_cache *hashtab_node_cachep; +/* + * Here we simply round the number of elements up to the nearest power of two. + * I tried also other options like rouding down or rounding to the closest + * power of two (up or down based on which is closer), but I was unable to + * find any significant difference in lookup/insert performance that would + * justify switching to a different (less intuitive) formula. It could be that + * a different formula is actually more optimal, but any future changes here + * should be supported with performance/memory usage data. + * + * The total memory used by the htable arrays (only) with Fedora policy loaded + * is approximately 163 KB at the time of writing. + */ +static u32 hashtab_compute_size(u32 nel) +{ + return nel == 0 ? 0 : roundup_pow_of_two(nel); +} + struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), - u32 size) + u32 nel_hint) { struct hashtab *p; - u32 i; + u32 i, size = hashtab_compute_size(nel_hint); p = kzalloc(sizeof(*p), GFP_KERNEL); if (!p) @@ -27,6 +44,9 @@ struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void * p->nel = 0; p->hash_value = hash_value; p->keycmp = keycmp; + if (!size) + return p; + p->htable = kmalloc_array(size, sizeof(*p->htable), GFP_KERNEL); if (!p->htable) { kfree(p); @@ -46,7 +66,7 @@ int hashtab_insert(struct hashtab *h, void *key, void *datum) cond_resched(); - if (!h || h->nel == HASHTAB_MAX_NODES) + if (!h || !h->size || h->nel == HASHTAB_MAX_NODES) return -EINVAL; hvalue = h->hash_value(h, key); @@ -82,7 +102,7 @@ void *hashtab_search(struct hashtab *h, const void *key) u32 hvalue; struct hashtab_node *cur; - if (!h) + if (!h || !h->size) return NULL; hvalue = h->hash_value(h, key); diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h index 3e3e42bfd150..dde54d9ff01c 100644 --- a/security/selinux/ss/hashtab.h +++ b/security/selinux/ss/hashtab.h @@ -42,7 +42,7 @@ struct hashtab_info { */ struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key), int (*keycmp)(struct hashtab *h, const void *key1, const void *key2), - u32 size); + u32 nel_hint); /* * Inserts the specified (key, datum) pair into the specified hash table. diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 32b3a8acf96f..7ca8c74efba3 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -56,17 +56,6 @@ static const char *symtab_name[SYM_NUM] = { }; #endif -static unsigned int symtab_sizes[SYM_NUM] = { - 2, - 32, - 16, - 512, - 128, - 16, - 16, - 16, -}; - struct policydb_compat_info { int version; int sym_num; @@ -478,20 +467,10 @@ static int policydb_init(struct policydb *p) memset(p, 0, sizeof(*p)); - for (i = 0; i < SYM_NUM; i++) { - rc = symtab_init(&p->symtab[i], symtab_sizes[i]); - if (rc) - goto out; - } - rc = avtab_init(&p->te_avtab); if (rc) goto out; - rc = roles_init(p); - if (rc) - goto out; - rc = cond_policydb_init(p); if (rc) goto out; @@ -503,20 +482,12 @@ static int policydb_init(struct policydb *p) goto out; } - p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256); - if (!p->range_tr) { - rc = -ENOMEM; - goto out; - } - ebitmap_init(&p->filename_trans_ttypes); ebitmap_init(&p->policycaps); ebitmap_init(&p->permissive_map); return 0; out: - hashtab_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); hashtab_destroy(p->symtab[i].table); @@ -1142,12 +1113,12 @@ static int common_read(struct policydb *p, struct hashtab *h, void *fp) len = le32_to_cpu(buf[0]); comdatum->value = le32_to_cpu(buf[1]); + nel = le32_to_cpu(buf[3]); - rc = symtab_init(&comdatum->permissions, PERM_SYMTAB_SIZE); + rc = symtab_init(&comdatum->permissions, nel); if (rc) goto bad; comdatum->permissions.nprim = le32_to_cpu(buf[2]); - nel = le32_to_cpu(buf[3]); rc = str_read(&key, GFP_KERNEL, fp, len); if (rc) @@ -1308,12 +1279,12 @@ static int class_read(struct policydb *p, struct hashtab *h, void *fp) len = le32_to_cpu(buf[0]); len2 = le32_to_cpu(buf[1]); cladatum->value = le32_to_cpu(buf[2]); + nel = le32_to_cpu(buf[4]); - rc = symtab_init(&cladatum->permissions, PERM_SYMTAB_SIZE); + rc = symtab_init(&cladatum->permissions, nel); if (rc) goto bad; cladatum->permissions.nprim = le32_to_cpu(buf[3]); - nel = le32_to_cpu(buf[4]); ncons = le32_to_cpu(buf[5]); @@ -1826,6 +1797,11 @@ static int range_read(struct policydb *p, void *fp) return rc; nel = le32_to_cpu(buf[0]); + + p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, nel); + if (!p->range_tr) + return -ENOMEM; + for (i = 0; i < nel; i++) { rc = -ENOMEM; rt = kzalloc(sizeof(*rt), GFP_KERNEL); @@ -2418,6 +2394,17 @@ int policydb_read(struct policydb *p, void *fp) goto bad; nprim = le32_to_cpu(buf[0]); nel = le32_to_cpu(buf[1]); + + rc = symtab_init(&p->symtab[i], nel); + if (rc) + goto out; + + if (i == SYM_ROLES) { + rc = roles_init(p); + if (rc) + goto out; + } + for (j = 0; j < nel; j++) { rc = read_f[i](p, p->symtab[i].table, fp); if (rc) diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h index 41ad78a1f17b..72e2932fb12d 100644 --- a/security/selinux/ss/policydb.h +++ b/security/selinux/ss/policydb.h @@ -321,8 +321,6 @@ 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); -#define PERM_SYMTAB_SIZE 32 - #define POLICYDB_CONFIG_MLS 1 /* the config flags related to unknown classes/perms are bits 2 and 3 */
Instead allocate hash tables with just the right size based on the actual number of elements (which is almost always known beforehand, we just need to defer the hashtab allocation to the right time). The only case when we don't know the size (with the current policy format) is the new filename transitions hashtable. Here I just left the existing value. After this patch, the time to load Fedora policy on x86_64 decreases from 790 ms to 167 ms. If the unconfined module is removed, it decreases from 750 ms to 122 ms. It is also likely that other operations are going to be faster, mainly string_to_context_struct() or mls_compute_sid(), but I didn't try to quantify that. The memory usage of all hash table arrays increases from ~58 KB to ~163 KB (with Fedora policy on x86_64). Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- Changed in v3: - switch to simpler and more logical hash size heuristic - add comment explaining the choice of the heuristic Changed in v2: - guard against h->size == 0 in hashtab_search() and hashtab_insert() security/selinux/ss/hashtab.c | 28 +++++++++++++++--- security/selinux/ss/hashtab.h | 2 +- security/selinux/ss/policydb.c | 53 +++++++++++++--------------------- security/selinux/ss/policydb.h | 2 -- 4 files changed, 45 insertions(+), 40 deletions(-)