[PATCH v2 0/2] libsepol: Grow hashtab dynamically

[PATCH v2 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.

v2: simplify entry insertion in hashtab_check_resize()

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

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

-- 
2.24.1

[PATCH v2 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>
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
-- 
2.24.1

[PATCH v2 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 | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
index 9590b359..21143b76 100644
--- a/libsepol/src/hashtab.c
+++ b/libsepol/src/hashtab.c
@@ -63,6 +63,45 @@ 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;
+
+	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) {
+			hvalue = h->hash_value(h, cur->key);
+			dst = &new_htable[hvalue];
+			while (*dst && h->keycmp(h, cur->key, (*dst)->key) > 0)
+				dst = &(*dst)->next;
+
+			next = cur->next;
+
+			cur->next = *dst;
+			*dst = cur;
+
+			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 +110,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