| Message ID | 20200219134522.230822-3-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | libsepol: Grow hashtab dynamically | expand |
On Wed, Feb 19, 2020 at 2:45 PM Ondrej Mosnacek <omosnace@redhat.com> 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@redhat.com> > --- > 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 >
On 2/19/20 8:45 AM, Ondrej Mosnacek 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@redhat.com> Acked-by: Stephen Smalley <sds@tycho.nsa.gov>
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; + + 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];
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@redhat.com> --- libsepol/src/hashtab.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+)