[PATCH 0/2] libsepol: Grow hashtab dynamically

[PATCH 0/2] libsepol: Grow hashtab dynamically

[Ondrej Mosnacek]

The first patch is just a cleanup to have a single hashtab function that
can add elements, simplifying slightly the second patch, which
implements the actual auto-growing of hash tables.

Please see the log messages of the patches for more details.

Ondrej Mosnacek (2):
  libsepol,newrole: remove unused hashtab functions
  libsepol: grow hashtab dynamically

 libsepol/include/sepol/policydb/hashtab.h |  28 -----
 libsepol/src/hashtab.c                    | 127 +++++++---------------
 policycoreutils/newrole/hashtab.c         |  85 ---------------
 policycoreutils/newrole/hashtab.h         |  28 -----
 4 files changed, 42 insertions(+), 226 deletions(-)

-- 
2.24.1

[PATCH 1/2] libsepol,newrole: remove unused hashtab functions

[Ondrej Mosnacek]

hashtab_replace() and hashtab_map_remove_on_error() aren't used
anywhere, no need to keep them around...

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsepol/include/sepol/policydb/hashtab.h | 28 --------
 libsepol/src/hashtab.c                    | 85 -----------------------
 policycoreutils/newrole/hashtab.c         | 85 -----------------------
 policycoreutils/newrole/hashtab.h         | 28 --------
 4 files changed, 226 deletions(-)

diff --git a/libsepol/include/sepol/policydb/hashtab.h b/libsepol/include/sepol/policydb/hashtab.h
index ca5ba862..dca8c983 100644
--- a/libsepol/include/sepol/policydb/hashtab.h
+++ b/libsepol/include/sepol/policydb/hashtab.h
@@ -79,20 +79,6 @@ extern int hashtab_remove(hashtab_t h, hashtab_key_t k,
 					   hashtab_datum_t d,
 					   void *args), void *args);
 
-/*
-   Insert or replace the specified (key, datum) pair in the specified
-   hash table.  If an entry for the specified key already exists,
-   then the specified destroy function is applied to (key,datum,args)
-   for the entry prior to replacing the entry's contents.
-
-   Returns SEPOL_ENOMEM if insufficient space is available or
-   SEPOL_OK otherwise.
- */
-extern int hashtab_replace(hashtab_t h, hashtab_key_t k, hashtab_datum_t d,
-			   void (*destroy) (hashtab_key_t k,
-					    hashtab_datum_t d,
-					    void *args), void *args);
-
 /*
    Searches for the entry with the specified key in the hash table.
 
@@ -122,20 +108,6 @@ extern int hashtab_map(hashtab_t h,
 				     hashtab_datum_t d,
 				     void *args), void *args);
 
-/*
-   Same as hashtab_map, except that if apply returns a non-zero status,
-   then the (key,datum) pair will be removed from the hashtab and the
-   destroy function will be applied to (key,datum,args).
- */
-extern void hashtab_map_remove_on_error(hashtab_t h,
-					int (*apply) (hashtab_key_t k,
-						      hashtab_datum_t d,
-						      void *args),
-					void (*destroy) (hashtab_key_t k,
-							 hashtab_datum_t d,
-							 void *args),
-					void *args);
-
 extern void hashtab_hash_eval(hashtab_t h, char *tag);
 
 #ifdef __cplusplus
diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
index f5407ab6..9590b359 100644
--- a/libsepol/src/hashtab.c
+++ b/libsepol/src/hashtab.c
@@ -133,48 +133,6 @@ int hashtab_remove(hashtab_t h, hashtab_key_t key,
 	return SEPOL_OK;
 }
 
-int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
-		    void (*destroy) (hashtab_key_t k,
-				     hashtab_datum_t d, void *args), void *args)
-{
-	int hvalue;
-	hashtab_ptr_t prev, cur, newnode;
-
-	if (!h)
-		return SEPOL_ENOMEM;
-
-	hvalue = h->hash_value(h, key);
-	prev = NULL;
-	cur = h->htable[hvalue];
-	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
-		prev = cur;
-		cur = cur->next;
-	}
-
-	if (cur && (h->keycmp(h, key, cur->key) == 0)) {
-		if (destroy)
-			destroy(cur->key, cur->datum, args);
-		cur->key = key;
-		cur->datum = datum;
-	} else {
-		newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
-		if (newnode == NULL)
-			return SEPOL_ENOMEM;
-		memset(newnode, 0, sizeof(struct hashtab_node));
-		newnode->key = key;
-		newnode->datum = datum;
-		if (prev) {
-			newnode->next = prev->next;
-			prev->next = newnode;
-		} else {
-			newnode->next = h->htable[hvalue];
-			h->htable[hvalue] = newnode;
-		}
-	}
-
-	return SEPOL_OK;
-}
-
 hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
 {
 
@@ -241,49 +199,6 @@ int hashtab_map(hashtab_t h,
 	return SEPOL_OK;
 }
 
-void hashtab_map_remove_on_error(hashtab_t h,
-				 int (*apply) (hashtab_key_t k,
-					       hashtab_datum_t d,
-					       void *args),
-				 void (*destroy) (hashtab_key_t k,
-						  hashtab_datum_t d,
-						  void *args), void *args)
-{
-	unsigned int i;
-	int ret;
-	hashtab_ptr_t last, cur, temp;
-
-	if (!h)
-		return;
-
-	for (i = 0; i < h->size; i++) {
-		last = NULL;
-		cur = h->htable[i];
-		while (cur != NULL) {
-			ret = apply(cur->key, cur->datum, args);
-			if (ret) {
-				if (last) {
-					last->next = cur->next;
-				} else {
-					h->htable[i] = cur->next;
-				}
-
-				temp = cur;
-				cur = cur->next;
-				if (destroy)
-					destroy(temp->key, temp->datum, args);
-				free(temp);
-				h->nel--;
-			} else {
-				last = cur;
-				cur = cur->next;
-			}
-		}
-	}
-
-	return;
-}
-
 void hashtab_hash_eval(hashtab_t h, char *tag)
 {
 	unsigned int i;
diff --git a/policycoreutils/newrole/hashtab.c b/policycoreutils/newrole/hashtab.c
index 24c65c49..bc502836 100644
--- a/policycoreutils/newrole/hashtab.c
+++ b/policycoreutils/newrole/hashtab.c
@@ -112,48 +112,6 @@ int hashtab_remove(hashtab_t h, hashtab_key_t key,
 	return HASHTAB_SUCCESS;
 }
 
-int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
-		    void (*destroy) (hashtab_key_t k,
-				     hashtab_datum_t d, void *args), void *args)
-{
-	int hvalue;
-	hashtab_ptr_t prev, cur, newnode;
-
-	if (!h)
-		return HASHTAB_OVERFLOW;
-
-	hvalue = h->hash_value(h, key);
-	prev = NULL;
-	cur = h->htable[hvalue];
-	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
-		prev = cur;
-		cur = cur->next;
-	}
-
-	if (cur && (h->keycmp(h, key, cur->key) == 0)) {
-		if (destroy)
-			destroy(cur->key, cur->datum, args);
-		cur->key = key;
-		cur->datum = datum;
-	} else {
-		newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
-		if (newnode == NULL)
-			return HASHTAB_OVERFLOW;
-		memset(newnode, 0, sizeof(struct hashtab_node));
-		newnode->key = key;
-		newnode->datum = datum;
-		if (prev) {
-			newnode->next = prev->next;
-			prev->next = newnode;
-		} else {
-			newnode->next = h->htable[hvalue];
-			h->htable[hvalue] = newnode;
-		}
-	}
-
-	return HASHTAB_SUCCESS;
-}
-
 hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
 {
 
@@ -220,49 +178,6 @@ int hashtab_map(hashtab_t h,
 	return HASHTAB_SUCCESS;
 }
 
-void hashtab_map_remove_on_error(hashtab_t h,
-				 int (*apply) (hashtab_key_t k,
-					       hashtab_datum_t d,
-					       void *args),
-				 void (*destroy) (hashtab_key_t k,
-						  hashtab_datum_t d,
-						  void *args), void *args)
-{
-	unsigned int i;
-	int ret;
-	hashtab_ptr_t last, cur, temp;
-
-	if (!h)
-		return;
-
-	for (i = 0; i < h->size; i++) {
-		last = NULL;
-		cur = h->htable[i];
-		while (cur != NULL) {
-			ret = apply(cur->key, cur->datum, args);
-			if (ret) {
-				if (last) {
-					last->next = cur->next;
-				} else {
-					h->htable[i] = cur->next;
-				}
-
-				temp = cur;
-				cur = cur->next;
-				if (destroy)
-					destroy(temp->key, temp->datum, args);
-				free(temp);
-				h->nel--;
-			} else {
-				last = cur;
-				cur = cur->next;
-			}
-		}
-	}
-
-	return;
-}
-
 void hashtab_hash_eval(hashtab_t h, char *tag)
 {
 	unsigned int i;
diff --git a/policycoreutils/newrole/hashtab.h b/policycoreutils/newrole/hashtab.h
index ad5559ba..092b96a9 100644
--- a/policycoreutils/newrole/hashtab.h
+++ b/policycoreutils/newrole/hashtab.h
@@ -81,20 +81,6 @@ extern int hashtab_remove(hashtab_t h, hashtab_key_t k,
 					   hashtab_datum_t d,
 					   void *args), void *args);
 
-/*
-   Insert or replace the specified (key, datum) pair in the specified
-   hash table.  If an entry for the specified key already exists,
-   then the specified destroy function is applied to (key,datum,args)
-   for the entry prior to replacing the entry's contents.
-
-   Returns HASHTAB_OVERFLOW if insufficient space is available or
-   HASHTAB_SUCCESS otherwise.
- */
-extern int hashtab_replace(hashtab_t h, hashtab_key_t k, hashtab_datum_t d,
-			   void (*destroy) (hashtab_key_t k,
-					    hashtab_datum_t d,
-					    void *args), void *args);
-
 /*
    Searches for the entry with the specified key in the hash table.
 
@@ -124,20 +110,6 @@ extern int hashtab_map(hashtab_t h,
 				     hashtab_datum_t d,
 				     void *args), void *args);
 
-/*
-   Same as hashtab_map, except that if apply returns a non-zero status,
-   then the (key,datum) pair will be removed from the hashtab and the
-   destroy function will be applied to (key,datum,args).
- */
-extern void hashtab_map_remove_on_error(hashtab_t h,
-					int (*apply) (hashtab_key_t k,
-						      hashtab_datum_t d,
-						      void *args),
-					void (*destroy) (hashtab_key_t k,
-							 hashtab_datum_t d,
-							 void *args),
-					void *args);
-
 extern void hashtab_hash_eval(hashtab_t h, char *tag);
 
 #endif
-- 
2.24.1

[PATCH 2/2] libsepol: grow hashtab dynamically

[Ondrej Mosnacek]

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;
+
+			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

Re: [PATCH 1/2] libsepol, newrole: remove unused hashtab functions

[Stephen Smalley]

On 2/19/20 8:45 AM, Ondrej Mosnacek wrote:
> hashtab_replace() and hashtab_map_remove_on_error() aren't used
> anywhere, no need to keep them around...
> 
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

Acked-by: Stephen Smalley <sds@tycho.nsa.gov>

> ---
>   libsepol/include/sepol/policydb/hashtab.h | 28 --------
>   libsepol/src/hashtab.c                    | 85 -----------------------
>   policycoreutils/newrole/hashtab.c         | 85 -----------------------
>   policycoreutils/newrole/hashtab.h         | 28 --------
>   4 files changed, 226 deletions(-)
> 
> diff --git a/libsepol/include/sepol/policydb/hashtab.h b/libsepol/include/sepol/policydb/hashtab.h
> index ca5ba862..dca8c983 100644
> --- a/libsepol/include/sepol/policydb/hashtab.h
> +++ b/libsepol/include/sepol/policydb/hashtab.h
> @@ -79,20 +79,6 @@ extern int hashtab_remove(hashtab_t h, hashtab_key_t k,
>   					   hashtab_datum_t d,
>   					   void *args), void *args);
>   
> -/*
> -   Insert or replace the specified (key, datum) pair in the specified
> -   hash table.  If an entry for the specified key already exists,
> -   then the specified destroy function is applied to (key,datum,args)
> -   for the entry prior to replacing the entry's contents.
> -
> -   Returns SEPOL_ENOMEM if insufficient space is available or
> -   SEPOL_OK otherwise.
> - */
> -extern int hashtab_replace(hashtab_t h, hashtab_key_t k, hashtab_datum_t d,
> -			   void (*destroy) (hashtab_key_t k,
> -					    hashtab_datum_t d,
> -					    void *args), void *args);
> -
>   /*
>      Searches for the entry with the specified key in the hash table.
>   
> @@ -122,20 +108,6 @@ extern int hashtab_map(hashtab_t h,
>   				     hashtab_datum_t d,
>   				     void *args), void *args);
>   
> -/*
> -   Same as hashtab_map, except that if apply returns a non-zero status,
> -   then the (key,datum) pair will be removed from the hashtab and the
> -   destroy function will be applied to (key,datum,args).
> - */
> -extern void hashtab_map_remove_on_error(hashtab_t h,
> -					int (*apply) (hashtab_key_t k,
> -						      hashtab_datum_t d,
> -						      void *args),
> -					void (*destroy) (hashtab_key_t k,
> -							 hashtab_datum_t d,
> -							 void *args),
> -					void *args);
> -
>   extern void hashtab_hash_eval(hashtab_t h, char *tag);
>   
>   #ifdef __cplusplus
> diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
> index f5407ab6..9590b359 100644
> --- a/libsepol/src/hashtab.c
> +++ b/libsepol/src/hashtab.c
> @@ -133,48 +133,6 @@ int hashtab_remove(hashtab_t h, hashtab_key_t key,
>   	return SEPOL_OK;
>   }
>   
> -int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
> -		    void (*destroy) (hashtab_key_t k,
> -				     hashtab_datum_t d, void *args), void *args)
> -{
> -	int hvalue;
> -	hashtab_ptr_t prev, cur, newnode;
> -
> -	if (!h)
> -		return SEPOL_ENOMEM;
> -
> -	hvalue = h->hash_value(h, key);
> -	prev = NULL;
> -	cur = h->htable[hvalue];
> -	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
> -		prev = cur;
> -		cur = cur->next;
> -	}
> -
> -	if (cur && (h->keycmp(h, key, cur->key) == 0)) {
> -		if (destroy)
> -			destroy(cur->key, cur->datum, args);
> -		cur->key = key;
> -		cur->datum = datum;
> -	} else {
> -		newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
> -		if (newnode == NULL)
> -			return SEPOL_ENOMEM;
> -		memset(newnode, 0, sizeof(struct hashtab_node));
> -		newnode->key = key;
> -		newnode->datum = datum;
> -		if (prev) {
> -			newnode->next = prev->next;
> -			prev->next = newnode;
> -		} else {
> -			newnode->next = h->htable[hvalue];
> -			h->htable[hvalue] = newnode;
> -		}
> -	}
> -
> -	return SEPOL_OK;
> -}
> -
>   hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
>   {
>   
> @@ -241,49 +199,6 @@ int hashtab_map(hashtab_t h,
>   	return SEPOL_OK;
>   }
>   
> -void hashtab_map_remove_on_error(hashtab_t h,
> -				 int (*apply) (hashtab_key_t k,
> -					       hashtab_datum_t d,
> -					       void *args),
> -				 void (*destroy) (hashtab_key_t k,
> -						  hashtab_datum_t d,
> -						  void *args), void *args)
> -{
> -	unsigned int i;
> -	int ret;
> -	hashtab_ptr_t last, cur, temp;
> -
> -	if (!h)
> -		return;
> -
> -	for (i = 0; i < h->size; i++) {
> -		last = NULL;
> -		cur = h->htable[i];
> -		while (cur != NULL) {
> -			ret = apply(cur->key, cur->datum, args);
> -			if (ret) {
> -				if (last) {
> -					last->next = cur->next;
> -				} else {
> -					h->htable[i] = cur->next;
> -				}
> -
> -				temp = cur;
> -				cur = cur->next;
> -				if (destroy)
> -					destroy(temp->key, temp->datum, args);
> -				free(temp);
> -				h->nel--;
> -			} else {
> -				last = cur;
> -				cur = cur->next;
> -			}
> -		}
> -	}
> -
> -	return;
> -}
> -
>   void hashtab_hash_eval(hashtab_t h, char *tag)
>   {
>   	unsigned int i;
> diff --git a/policycoreutils/newrole/hashtab.c b/policycoreutils/newrole/hashtab.c
> index 24c65c49..bc502836 100644
> --- a/policycoreutils/newrole/hashtab.c
> +++ b/policycoreutils/newrole/hashtab.c
> @@ -112,48 +112,6 @@ int hashtab_remove(hashtab_t h, hashtab_key_t key,
>   	return HASHTAB_SUCCESS;
>   }
>   
> -int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum,
> -		    void (*destroy) (hashtab_key_t k,
> -				     hashtab_datum_t d, void *args), void *args)
> -{
> -	int hvalue;
> -	hashtab_ptr_t prev, cur, newnode;
> -
> -	if (!h)
> -		return HASHTAB_OVERFLOW;
> -
> -	hvalue = h->hash_value(h, key);
> -	prev = NULL;
> -	cur = h->htable[hvalue];
> -	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
> -		prev = cur;
> -		cur = cur->next;
> -	}
> -
> -	if (cur && (h->keycmp(h, key, cur->key) == 0)) {
> -		if (destroy)
> -			destroy(cur->key, cur->datum, args);
> -		cur->key = key;
> -		cur->datum = datum;
> -	} else {
> -		newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
> -		if (newnode == NULL)
> -			return HASHTAB_OVERFLOW;
> -		memset(newnode, 0, sizeof(struct hashtab_node));
> -		newnode->key = key;
> -		newnode->datum = datum;
> -		if (prev) {
> -			newnode->next = prev->next;
> -			prev->next = newnode;
> -		} else {
> -			newnode->next = h->htable[hvalue];
> -			h->htable[hvalue] = newnode;
> -		}
> -	}
> -
> -	return HASHTAB_SUCCESS;
> -}
> -
>   hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
>   {
>   
> @@ -220,49 +178,6 @@ int hashtab_map(hashtab_t h,
>   	return HASHTAB_SUCCESS;
>   }
>   
> -void hashtab_map_remove_on_error(hashtab_t h,
> -				 int (*apply) (hashtab_key_t k,
> -					       hashtab_datum_t d,
> -					       void *args),
> -				 void (*destroy) (hashtab_key_t k,
> -						  hashtab_datum_t d,
> -						  void *args), void *args)
> -{
> -	unsigned int i;
> -	int ret;
> -	hashtab_ptr_t last, cur, temp;
> -
> -	if (!h)
> -		return;
> -
> -	for (i = 0; i < h->size; i++) {
> -		last = NULL;
> -		cur = h->htable[i];
> -		while (cur != NULL) {
> -			ret = apply(cur->key, cur->datum, args);
> -			if (ret) {
> -				if (last) {
> -					last->next = cur->next;
> -				} else {
> -					h->htable[i] = cur->next;
> -				}
> -
> -				temp = cur;
> -				cur = cur->next;
> -				if (destroy)
> -					destroy(temp->key, temp->datum, args);
> -				free(temp);
> -				h->nel--;
> -			} else {
> -				last = cur;
> -				cur = cur->next;
> -			}
> -		}
> -	}
> -
> -	return;
> -}
> -
>   void hashtab_hash_eval(hashtab_t h, char *tag)
>   {
>   	unsigned int i;
> diff --git a/policycoreutils/newrole/hashtab.h b/policycoreutils/newrole/hashtab.h
> index ad5559ba..092b96a9 100644
> --- a/policycoreutils/newrole/hashtab.h
> +++ b/policycoreutils/newrole/hashtab.h
> @@ -81,20 +81,6 @@ extern int hashtab_remove(hashtab_t h, hashtab_key_t k,
>   					   hashtab_datum_t d,
>   					   void *args), void *args);
>   
> -/*
> -   Insert or replace the specified (key, datum) pair in the specified
> -   hash table.  If an entry for the specified key already exists,
> -   then the specified destroy function is applied to (key,datum,args)
> -   for the entry prior to replacing the entry's contents.
> -
> -   Returns HASHTAB_OVERFLOW if insufficient space is available or
> -   HASHTAB_SUCCESS otherwise.
> - */
> -extern int hashtab_replace(hashtab_t h, hashtab_key_t k, hashtab_datum_t d,
> -			   void (*destroy) (hashtab_key_t k,
> -					    hashtab_datum_t d,
> -					    void *args), void *args);
> -
>   /*
>      Searches for the entry with the specified key in the hash table.
>   
> @@ -124,20 +110,6 @@ extern int hashtab_map(hashtab_t h,
>   				     hashtab_datum_t d,
>   				     void *args), void *args);
>   
> -/*
> -   Same as hashtab_map, except that if apply returns a non-zero status,
> -   then the (key,datum) pair will be removed from the hashtab and the
> -   destroy function will be applied to (key,datum,args).
> - */
> -extern void hashtab_map_remove_on_error(hashtab_t h,
> -					int (*apply) (hashtab_key_t k,
> -						      hashtab_datum_t d,
> -						      void *args),
> -					void (*destroy) (hashtab_key_t k,
> -							 hashtab_datum_t d,
> -							 void *args),
> -					void *args);
> -
>   extern void hashtab_hash_eval(hashtab_t h, char *tag);
>   
>   #endif
> 

Re: [PATCH 2/2] libsepol: grow hashtab dynamically

[Ondrej Mosnacek]

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
>


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

Re: [PATCH 2/2] libsepol: grow hashtab dynamically

[Stephen Smalley]

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>