On Wed, Feb 19, 2020 at 2:45 PM Ondrej Mosnacek <omosnace@xxxxxxxxxx> wrote:
> Detect when the hashtab's load factor gets too high and try to grow it
> and rehash it in such case. If the reallocation fails, just keep the
> hashtab at its current size, since this is not a fatal error (it will
> just be slower).
>
> This speeds up semodule -BN on Fedora from ~8.9s to ~7.2s (1.7 seconds
> saved).
>
> Signed-off-by: Ondrej Mosnacek <omosnace@xxxxxxxxxx>
> ---
> libsepol/src/hashtab.c | 42 ++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 42 insertions(+)
>
> diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
> index 9590b359..fe9c55b8 100644
> --- a/libsepol/src/hashtab.c
> +++ b/libsepol/src/hashtab.c
> @@ -63,6 +63,46 @@ hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
> return p;
> }
>
> +static void hashtab_check_resize(hashtab_t h)
> +{
> + unsigned int hvalue, i, old_size, new_size = h->size;
> + hashtab_ptr_t *new_htable, *dst, cur, next, tmp;
> +
> + while (new_size <= h->nel && new_size * 2 != 0)
> + new_size *= 2;
> +
> + if (h->size == new_size)
> + return;
> +
> + new_htable = calloc(new_size, sizeof(*new_htable));
> + if (!new_htable)
> + return;
> +
> + old_size = h->size;
> + h->size = new_size;
> +
> + /* Move all elements to the new htable */
> + for (i = 0; i < old_size; i++) {
> + cur = h->htable[i];
> + while (cur != NULL) {
> + next = cur->next;
> +
> + hvalue = h->hash_value(h, cur->key);
> + dst = &new_htable[hvalue];
> + while (*dst && h->keycmp(h, cur->key, (*dst)->key) > 0)
> + dst = &(*dst)->next;
> +
> + tmp = *dst;
> + *dst = cur;
> + cur->next = tmp;
I just realized that I can get rid of one assignment and the 'tmp' variable:
https://github.com/WOnder93/selinux/commit/a43e718d20b30603e1a8cd428c8d8b656a672153
Let me respin the patch...
> +
> + cur = next;
> + }
> + }
> + free(h->htable);
> + h->htable = new_htable;
> +}
> +
> int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
> {
> int hvalue;
> @@ -71,6 +111,8 @@ int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
> if (!h)
> return SEPOL_ENOMEM;
>
> + hashtab_check_resize(h);
> +
> hvalue = h->hash_value(h, key);
> prev = NULL;
> cur = h->htable[hvalue];
> --
> 2.24.1
>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
