[PATCH] selinux: reduce the use of hard-coded hash sizes

[PATCH] selinux: reduce the use of hard-coded hash sizes

[Ondrej Mosnacek]

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 950 ms to 220 ms. If the unconfined module is removed, it decreases
from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
(it is hard to measure precisely). I believe it is a small price to pay
for the increased performance.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 security/selinux/ss/hashtab.c  | 21 ++++++++++++--
 security/selinux/ss/hashtab.h  |  2 +-
 security/selinux/ss/policydb.c | 53 +++++++++++++---------------------
 security/selinux/ss/policydb.h |  2 --
 4 files changed, 40 insertions(+), 38 deletions(-)

diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
index ebfdaa31ee32..554a91ef3f06 100644
--- a/security/selinux/ss/hashtab.c
+++ b/security/selinux/ss/hashtab.c
@@ -12,12 +12,26 @@
 
 static struct kmem_cache *hashtab_node_cachep;
 
+static u32 hashtab_compute_size(u32 nel)
+{
+	u32 size;
+
+	if (nel <= 2)
+		return nel;
+
+	/* use the nearest power of two to balance size and access time */
+	size = roundup_pow_of_two(nel);
+	if (size - nel > size / 4)
+		size /= 2;
+	return size;
+}
+
 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 +41,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);
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 7bc791639d5b..b123cad55d66 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);
@@ -2419,6 +2395,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 */
-- 
2.24.1

Re: [PATCH] selinux: reduce the use of hard-coded hash sizes

[Ondrej Mosnacek]

On Mon, Feb 17, 2020 at 12:49 PM 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 950 ms to 220 ms. If the unconfined module is removed, it decreases
> from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
> (it is hard to measure precisely). I believe it is a small price to pay
> for the increased performance.
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>  security/selinux/ss/hashtab.c  | 21 ++++++++++++--
>  security/selinux/ss/hashtab.h  |  2 +-
>  security/selinux/ss/policydb.c | 53 +++++++++++++---------------------
>  security/selinux/ss/policydb.h |  2 --
>  4 files changed, 40 insertions(+), 38 deletions(-)

Note: This patch applies on top of the filename transition series [1].

[1] https://lore.kernel.org/selinux/20200212112255.105678-1-omosnace@redhat.com/T/

-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [PATCH] selinux: reduce the use of hard-coded hash sizes

[Stephen Smalley]

On 2/17/20 6:49 AM, Ondrej Mosnacek 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 950 ms to 220 ms. If the unconfined module is removed, it decreases
> from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
> (it is hard to measure precisely). I believe it is a small price to pay
> for the increased performance.
> 
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>   security/selinux/ss/hashtab.c  | 21 ++++++++++++--
>   security/selinux/ss/hashtab.h  |  2 +-
>   security/selinux/ss/policydb.c | 53 +++++++++++++---------------------
>   security/selinux/ss/policydb.h |  2 --
>   4 files changed, 40 insertions(+), 38 deletions(-)
> 
> diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
> index ebfdaa31ee32..554a91ef3f06 100644
> --- a/security/selinux/ss/hashtab.c
> +++ b/security/selinux/ss/hashtab.c
> @@ -27,6 +41,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);

Thanks, this looks promising.  However, I was wondering: if we end up 
with size == 0 (e.g. policy happens to have an empty table), does the 
rest of the hashtab_* code always correctly handle the fact that 
->htable could be NULL?  Doesn't look obviously safe to me on a quick look.

Re: [PATCH] selinux: reduce the use of hard-coded hash sizes

[Ondrej Mosnacek]

On Tue, Feb 18, 2020 at 3:59 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 2/17/20 6:49 AM, Ondrej Mosnacek 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 950 ms to 220 ms. If the unconfined module is removed, it decreases
> > from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
> > (it is hard to measure precisely). I believe it is a small price to pay
> > for the increased performance.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > ---
> >   security/selinux/ss/hashtab.c  | 21 ++++++++++++--
> >   security/selinux/ss/hashtab.h  |  2 +-
> >   security/selinux/ss/policydb.c | 53 +++++++++++++---------------------
> >   security/selinux/ss/policydb.h |  2 --
> >   4 files changed, 40 insertions(+), 38 deletions(-)
> >
> > diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
> > index ebfdaa31ee32..554a91ef3f06 100644
> > --- a/security/selinux/ss/hashtab.c
> > +++ b/security/selinux/ss/hashtab.c
> > @@ -27,6 +41,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);
>
> Thanks, this looks promising.  However, I was wondering: if we end up
> with size == 0 (e.g. policy happens to have an empty table), does the
> rest of the hashtab_* code always correctly handle the fact that
> ->htable could be NULL?  Doesn't look obviously safe to me on a quick look.

Hm... it seems I didn't think this through when I was trying to handle
this case. I was rebasing this patch all over the place as I was
working on other changes in parallel, so maybe I just lost the safety
somewhere along the way... I think I will just clamp the minimum size
to 1, as that seems both safer and simpler. The extra 8-byte
allocation shouldn't cost much (there are only O(number of classes +
commons) hash tables and these make no sense to have 0 entries).

--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [PATCH] selinux: reduce the use of hard-coded hash sizes

[Stephen Smalley]

On 2/18/20 10:21 AM, Ondrej Mosnacek wrote:
> On Tue, Feb 18, 2020 at 3:59 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
>> On 2/17/20 6:49 AM, Ondrej Mosnacek 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 950 ms to 220 ms. If the unconfined module is removed, it decreases
>>> from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
>>> (it is hard to measure precisely). I believe it is a small price to pay
>>> for the increased performance.
>>>
>>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>>> ---
>>>    security/selinux/ss/hashtab.c  | 21 ++++++++++++--
>>>    security/selinux/ss/hashtab.h  |  2 +-
>>>    security/selinux/ss/policydb.c | 53 +++++++++++++---------------------
>>>    security/selinux/ss/policydb.h |  2 --
>>>    4 files changed, 40 insertions(+), 38 deletions(-)
>>>
>>> diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
>>> index ebfdaa31ee32..554a91ef3f06 100644
>>> --- a/security/selinux/ss/hashtab.c
>>> +++ b/security/selinux/ss/hashtab.c
>>> @@ -27,6 +41,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);
>>
>> Thanks, this looks promising.  However, I was wondering: if we end up
>> with size == 0 (e.g. policy happens to have an empty table), does the
>> rest of the hashtab_* code always correctly handle the fact that
>> ->htable could be NULL?  Doesn't look obviously safe to me on a quick look.
> 
> Hm... it seems I didn't think this through when I was trying to handle
> this case. I was rebasing this patch all over the place as I was
> working on other changes in parallel, so maybe I just lost the safety
> somewhere along the way... I think I will just clamp the minimum size
> to 1, as that seems both safer and simpler. The extra 8-byte
> allocation shouldn't cost much (there are only O(number of classes +
> commons) hash tables and these make no sense to have 0 entries).

Hmm...on booting this kernel, I am seeing a number of calls to 
hashtab_create() with nel_hint==0 leading to size == 0 and nothing is 
obviously breaking, so maybe this is safe?

Re: [PATCH] selinux: reduce the use of hard-coded hash sizes

[Stephen Smalley]

On 2/18/20 11:18 AM, Stephen Smalley wrote:
> On 2/18/20 10:21 AM, Ondrej Mosnacek wrote:
>> On Tue, Feb 18, 2020 at 3:59 PM Stephen Smalley <sds@tycho.nsa.gov> 
>> wrote:
>>> On 2/17/20 6:49 AM, Ondrej Mosnacek 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 950 ms to 220 ms. If the unconfined module is removed, it 
>>>> decreases
>>>> from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
>>>> (it is hard to measure precisely). I believe it is a small price to pay
>>>> for the increased performance.
>>>>
>>>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>>>> ---
>>>>    security/selinux/ss/hashtab.c  | 21 ++++++++++++--
>>>>    security/selinux/ss/hashtab.h  |  2 +-
>>>>    security/selinux/ss/policydb.c | 53 
>>>> +++++++++++++---------------------
>>>>    security/selinux/ss/policydb.h |  2 --
>>>>    4 files changed, 40 insertions(+), 38 deletions(-)
>>>>
>>>> diff --git a/security/selinux/ss/hashtab.c 
>>>> b/security/selinux/ss/hashtab.c
>>>> index ebfdaa31ee32..554a91ef3f06 100644
>>>> --- a/security/selinux/ss/hashtab.c
>>>> +++ b/security/selinux/ss/hashtab.c
>>>> @@ -27,6 +41,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);
>>>
>>> Thanks, this looks promising.  However, I was wondering: if we end up
>>> with size == 0 (e.g. policy happens to have an empty table), does the
>>> rest of the hashtab_* code always correctly handle the fact that
>>> ->htable could be NULL?  Doesn't look obviously safe to me on a quick 
>>> look.
>>
>> Hm... it seems I didn't think this through when I was trying to handle
>> this case. I was rebasing this patch all over the place as I was
>> working on other changes in parallel, so maybe I just lost the safety
>> somewhere along the way... I think I will just clamp the minimum size
>> to 1, as that seems both safer and simpler. The extra 8-byte
>> allocation shouldn't cost much (there are only O(number of classes +
>> commons) hash tables and these make no sense to have 0 entries).
> 
> Hmm...on booting this kernel, I am seeing a number of calls to 
> hashtab_create() with nel_hint==0 leading to size == 0 and nothing is 
> obviously breaking, so maybe this is safe?

I guess this happens for any class that doesn't define any of its own 
permissions (beyond the inherited common ones).  Probably could just add 
some simple checks to hashtab_* where absent to ensure we don't ever 
dereference ->htable if NULL.

Re: [PATCH] selinux: reduce the use of hard-coded hash sizes

[Ondrej Mosnacek]

On Tue, Feb 18, 2020 at 5:44 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 2/18/20 11:18 AM, Stephen Smalley wrote:
> > On 2/18/20 10:21 AM, Ondrej Mosnacek wrote:
> >> On Tue, Feb 18, 2020 at 3:59 PM Stephen Smalley <sds@tycho.nsa.gov>
> >> wrote:
> >>> On 2/17/20 6:49 AM, Ondrej Mosnacek 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 950 ms to 220 ms. If the unconfined module is removed, it
> >>>> decreases
> >>>> from 870 ms to 170 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 increases a bit after this patch, but only by ~1-2 MB
> >>>> (it is hard to measure precisely). I believe it is a small price to pay
> >>>> for the increased performance.
> >>>>
> >>>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> >>>> ---
> >>>>    security/selinux/ss/hashtab.c  | 21 ++++++++++++--
> >>>>    security/selinux/ss/hashtab.h  |  2 +-
> >>>>    security/selinux/ss/policydb.c | 53
> >>>> +++++++++++++---------------------
> >>>>    security/selinux/ss/policydb.h |  2 --
> >>>>    4 files changed, 40 insertions(+), 38 deletions(-)
> >>>>
> >>>> diff --git a/security/selinux/ss/hashtab.c
> >>>> b/security/selinux/ss/hashtab.c
> >>>> index ebfdaa31ee32..554a91ef3f06 100644
> >>>> --- a/security/selinux/ss/hashtab.c
> >>>> +++ b/security/selinux/ss/hashtab.c
> >>>> @@ -27,6 +41,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);
> >>>
> >>> Thanks, this looks promising.  However, I was wondering: if we end up
> >>> with size == 0 (e.g. policy happens to have an empty table), does the
> >>> rest of the hashtab_* code always correctly handle the fact that
> >>> ->htable could be NULL?  Doesn't look obviously safe to me on a quick
> >>> look.
> >>
> >> Hm... it seems I didn't think this through when I was trying to handle
> >> this case. I was rebasing this patch all over the place as I was
> >> working on other changes in parallel, so maybe I just lost the safety
> >> somewhere along the way... I think I will just clamp the minimum size
> >> to 1, as that seems both safer and simpler. The extra 8-byte
> >> allocation shouldn't cost much (there are only O(number of classes +
> >> commons) hash tables and these make no sense to have 0 entries).
> >
> > Hmm...on booting this kernel, I am seeing a number of calls to
> > hashtab_create() with nel_hint==0 leading to size == 0 and nothing is
> > obviously breaking, so maybe this is safe?
>
> I guess this happens for any class that doesn't define any of its own
> permissions (beyond the inherited common ones).  Probably could just add
> some simple checks to hashtab_* where absent to ensure we don't ever
> dereference ->htable if NULL.

Yeah, OK. I only needed to add a check to hashtab_insert() and
hashtab_search(), the rest will already do the sane thing as-is.

-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.