Skip to contentSkip to conversation

libsepol/tests: add ebitmap tests

PATCH Superseded Christian Göttsche 2 participants 14 messages Jul 12, 2022 – Jul 18, 2022 SELinux security module

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/7 libsepol/tests: add ebitmap tests

Preparation for several ebitmap related optimizations.

---
 libsepol/tests/libsepol-tests.c |   2 +
 libsepol/tests/test-ebitmap.c   | 711 ++++++++++++++++++++++++++++++++
 libsepol/tests/test-ebitmap.h   |  10 +
 3 files changed, 723 insertions(+)
 create mode 100644 libsepol/tests/test-ebitmap.c
 create mode 100644 libsepol/tests/test-ebitmap.h
libsepol/tests/libsepol-tests.c +2 -0
index dc8fd5ce..5ae6bedc 100644
@@ -19,6 +19,7 @@
  */
 
 #include "test-cond.h"
+#include "test-ebitmap.h"
 #include "test-linker.h"
 #include "test-expander.h"
 #include "test-deps.h"
@@ -64,6 +65,7 @@ static bool do_tests(int interactive, int verbose)
 	if (CUE_SUCCESS != CU_initialize_registry())
 		return CU_get_error();
 
+	DECLARE_SUITE(ebitmap);
 	DECLARE_SUITE(cond);
 	DECLARE_SUITE(linker);
 	DECLARE_SUITE(expander);
libsepol/tests/test-ebitmap.c new file +711 -0

711 lines not on this page · raw message

libsepol/tests/test-ebitmap.h new file +10 -0
new file mode 100644
index 00000000..952a0421
@@ -0,0 +1,10 @@
+#ifndef TEST_EBITMAP_H__
+#define TEST_EBITMAP_H__
+
+#include <CUnit/Basic.h>
+
+int ebitmap_test_init(void);
+int ebitmap_test_cleanup(void);
+int ebitmap_add_tests(CU_pSuite suite);
+
+#endif  /* TEST_EBITMAP_H__ */
Signature · 1 line
2.36.1
#1 lore raw

PATCH 2/7 libsepol: add ebitmap_init_range

Add an initializer for ebitmaps that sets all bits in a given range to save node traversals for each bit to set, compared to calling ebitmap_init() followed by iterating ebitmap_set_bit().

---
 libsepol/include/sepol/policydb/ebitmap.h |  1 +
 libsepol/src/ebitmap.c                    | 49 +++++++++++++++++++++++
 libsepol/tests/test-ebitmap.c             | 32 +++++++++++++++
 3 files changed, 82 insertions(+)
libsepol/include/sepol/policydb/ebitmap.h +1 -0
index 81d0c7a6..85b7ccfb 100644
@@ -94,6 +94,7 @@ extern int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2);
 extern int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2);
 extern int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit);
 extern int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value);
+extern int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit);
 extern unsigned int ebitmap_highest_set_bit(const ebitmap_t * e);
 extern void ebitmap_destroy(ebitmap_t * e);
 extern int ebitmap_read(ebitmap_t * e, void *fp);
libsepol/src/ebitmap.c +49 -0

55 lines not on this page · raw message

libsepol/tests/test-ebitmap.c +32 -0
index a21f18c0..1a49aa5f 100644
@@ -135,6 +135,37 @@ static void test_ebitmap_set_and_get(void)
 	ebitmap_destroy(&e);
 }
 
+static void test_ebitmap_init_range(void)
+{
+	ebitmap_t e1, e2, e3, e4, e5, e6;
+
+	CU_ASSERT_EQUAL(ebitmap_init_range(&e1, 0, 0), 0);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e1), 0);
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e1), 1);
+
+	CU_ASSERT_EQUAL(ebitmap_init_range(&e2, 0, 5), 0);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e2), 5);
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e2), 6);
+
+	CU_ASSERT_EQUAL(ebitmap_init_range(&e3, 20, 100), 0);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e3), 100);
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e3), 81);
+
+	CU_ASSERT_EQUAL(ebitmap_init_range(&e4, 100, 400), 0);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e4), 400);
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e4), 301);
+
+	CU_ASSERT_EQUAL(ebitmap_init_range(&e5, 10, 5), -EINVAL);
+	CU_ASSERT_EQUAL(ebitmap_init_range(&e6, 0, UINT32_MAX), -EOVERFLOW);
+
+	ebitmap_destroy(&e6);
+	ebitmap_destroy(&e5);
+	ebitmap_destroy(&e4);
+	ebitmap_destroy(&e3);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
 static void test_ebitmap_or(void)
 {
 	ebitmap_t e1, e2, e3, e4;
@@ -701,6 +732,7 @@ int ebitmap_add_tests(CU_pSuite suite)
 	ADD_TEST(ebitmap_init_destroy);
 	ADD_TEST(ebitmap_cmp);
 	ADD_TEST(ebitmap_set_and_get);
+	ADD_TEST(ebitmap_init_range);
 	ADD_TEST(ebitmap_or);
 	ADD_TEST(ebitmap_and);
 	ADD_TEST(ebitmap_xor);
Signature · 1 line
2.36.1
#2 lore raw

Re: [PATCH 2/7] libsepol: add ebitmap_init_range

Quoted 59 lines · Christian Göttsche

Add an initializer for ebitmaps that sets all bits in a given range to save node traversals for each bit to set, compared to calling ebitmap_init() followed by iterating ebitmap_set_bit().

---
 libsepol/include/sepol/policydb/ebitmap.h |  1 +
 libsepol/src/ebitmap.c                    | 49 +++++++++++++++++++++++
 libsepol/tests/test-ebitmap.c             | 32 +++++++++++++++
 3 files changed, 82 insertions(+)
libsepol/include/sepol/policydb/ebitmap.h +1 -0
index 81d0c7a6..85b7ccfb 100644
@@ -94,6 +94,7 @@ extern int ebitmap_contains(const ebitmap_t * e1, const ebitmap_t * e2);
 extern int ebitmap_match_any(const ebitmap_t *e1, const ebitmap_t *e2);
 extern int ebitmap_get_bit(const ebitmap_t * e, unsigned int bit);
 extern int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value);
+extern int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit);
 extern unsigned int ebitmap_highest_set_bit(const ebitmap_t * e);
 extern void ebitmap_destroy(ebitmap_t * e);
 extern int ebitmap_read(ebitmap_t * e, void *fp);
libsepol/src/ebitmap.c +27 -0
index bd98c0f8..fb20e994 100644
@@ -349,6 +349,55 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
        return 0;
 }
 
+int ebitmap_init_range(ebitmap_t * e, unsigned int minbit, unsigned int maxbit)
+{
+       ebitmap_node_t *new, *prev = NULL;
+       uint32_t minstartbit = minbit & ~(MAPSIZE - 1);
+       uint32_t maxstartbit = maxbit & ~(MAPSIZE - 1);
+       uint32_t minhighbit = minstartbit + MAPSIZE;
+       uint32_t maxhighbit = maxstartbit + MAPSIZE;
+       uint32_t startbit;
+       MAPTYPE mask;
+
+       ebitmap_init(e);
+
+       if (minbit > maxbit)
+               return -EINVAL;
+
+       if (minhighbit == 0 || maxhighbit == 0)
+               return -EOVERFLOW;
+
+       for (startbit = minstartbit; startbit <= maxstartbit; startbit += MAPSIZE) {
+               new = malloc(sizeof(ebitmap_node_t));
+               if (!new)
+                       return -ENOMEM;
+
+               new->next = NULL;
+               new->startbit = startbit;
+
+               if (startbit != minstartbit && startbit != maxstartbit)

libsepol/src/ebitmap.c int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value) · line 388

Quoted 10 lines
libsepol/src/ebitmap.c +10 -0
+                       new->map = ~((MAPTYPE)0);
+               else if (startbit != maxstartbit)
+                       new->map = ~((MAPTYPE)0) << (minbit - startbit);
+               else if (startbit != minstartbit)
+                       new->map = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - startbit + 1));
+               else {
+                       mask = ~((MAPTYPE)0) >> (MAPSIZE - (maxbit - minbit + 1));
+                       new->map = (mask << (minbit - startbit));
+               }
+

I view braces in if-else statements as all or nothing. If you need them for one clause, then use them for all clauses.

Everything else about this patch looks good.

Thanks,
Jim

Quoted 68 lines
libsepol/src/ebitmap.c +12 -0
+               if (prev)
+                       prev->next = new;
+               else
+                       e->node = new;
+               prev = new;
+       }
+
+       e->highbit = maxhighbit;
+
+       return 0;
+}
+
 unsigned int ebitmap_highest_set_bit(const ebitmap_t * e)
 {
        const ebitmap_node_t *n;
libsepol/tests/test-ebitmap.c +32 -1
index a21f18c0..1a49aa5f 100644
@@ -135,6 +135,37 @@ static void test_ebitmap_set_and_get(void)
        ebitmap_destroy(&e);
 }
 
+static void test_ebitmap_init_range(void)
+{
+       ebitmap_t e1, e2, e3, e4, e5, e6;
+
+       CU_ASSERT_EQUAL(ebitmap_init_range(&e1, 0, 0), 0);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e1), 0);
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e1), 1);
+
+       CU_ASSERT_EQUAL(ebitmap_init_range(&e2, 0, 5), 0);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e2), 5);
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e2), 6);
+
+       CU_ASSERT_EQUAL(ebitmap_init_range(&e3, 20, 100), 0);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e3), 100);
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e3), 81);
+
+       CU_ASSERT_EQUAL(ebitmap_init_range(&e4, 100, 400), 0);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e4), 400);
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e4), 301);
+
+       CU_ASSERT_EQUAL(ebitmap_init_range(&e5, 10, 5), -EINVAL);
+       CU_ASSERT_EQUAL(ebitmap_init_range(&e6, 0, UINT32_MAX), -EOVERFLOW);
+
+       ebitmap_destroy(&e6);
+       ebitmap_destroy(&e5);
+       ebitmap_destroy(&e4);
+       ebitmap_destroy(&e3);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
 static void test_ebitmap_or(void)
 {
        ebitmap_t e1, e2, e3, e4;
@@ -701,6 +732,7 @@ int ebitmap_add_tests(CU_pSuite suite)
        ADD_TEST(ebitmap_init_destroy);
        ADD_TEST(ebitmap_cmp);
        ADD_TEST(ebitmap_set_and_get);
+       ADD_TEST(ebitmap_init_range);
        ADD_TEST(ebitmap_or);
        ADD_TEST(ebitmap_and);
        ADD_TEST(ebitmap_xor);
--

2.36.1

#3 lore raw

PATCH 3/7 libsepol/cil: use ebitmap_init_range

In reply to Christian Göttsche

Especially in the case of __cil_permissionx_expr_range_to_bitmap_helper() it substitutes hundreds of thousand of calls to ebitmap_set_bit() during semodule(8) on a policy widely using extended permissions.

---
 libsepol/cil/src/cil_post.c | 30 +++++++++---------------------
 1 file changed, 9 insertions(+), 21 deletions(-)
libsepol/cil/src/cil_post.c +9 -21
index 714ce227..6e95225f 100644
@@ -1191,7 +1191,6 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, struc
 	struct cil_tree_node *n2 = d2->nodes->head->data;
 	struct cil_cat *c1 = (struct cil_cat *)d1;
 	struct cil_cat *c2 = (struct cil_cat *)d2;
-	int i;
 
 	if (n1->flavor == CIL_CATSET || n2->flavor == CIL_CATSET) {
 		cil_log(CIL_ERR, "Category sets cannont be used in a category range\n");
@@ -1213,12 +1212,10 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, struc
 		goto exit;
 	}
 
-	for (i = c1->value; i <= c2->value; i++) {
-		if (ebitmap_set_bit(bitmap, i, 1)) {
-			cil_log(CIL_ERR, "Failed to set cat bit\n");
-			ebitmap_destroy(bitmap);
-			goto exit;
-		}
+	if (ebitmap_init_range(bitmap, c1->value, c2->value)) {
+		cil_log(CIL_ERR, "Failed to set cat bit\n");
+		ebitmap_destroy(bitmap);
+		goto exit;
 	}
 
 	return SEPOL_OK;
@@ -1234,7 +1231,6 @@ static int __cil_permissionx_expr_range_to_bitmap_helper(struct cil_list_item *i
 	char *p2 = i2->data;
 	uint16_t v1;
 	uint16_t v2;
-	uint32_t i;
 
 	rc = __cil_permx_str_to_int(p1, &v1);
 	if (rc != SEPOL_OK) {
@@ -1246,12 +1242,10 @@ static int __cil_permissionx_expr_range_to_bitmap_helper(struct cil_list_item *i
 		goto exit;
 	}
 
-	for (i = v1; i <= v2; i++) {
-		if (ebitmap_set_bit(bitmap, i, 1)) {
-			cil_log(CIL_ERR, "Failed to set permissionx bit\n");
-			ebitmap_destroy(bitmap);
-			goto exit;
-		}
+	if (ebitmap_init_range(bitmap, v1, v2)) {
+		cil_log(CIL_ERR, "Failed to set permissionx bits\n");
+		ebitmap_destroy(bitmap);
+		goto exit;
 	}
 
 	return SEPOL_OK;
@@ -1318,9 +1312,7 @@ static int __cil_expr_to_bitmap(struct cil_list *expr, ebitmap_t *out, int max,
 		enum cil_flavor op = (enum cil_flavor)(uintptr_t)curr->data;
 
 		if (op == CIL_ALL) {
-			ebitmap_init(&b1); /* all zeros */
-			rc = ebitmap_not(&tmp, &b1, max);
-			ebitmap_destroy(&b1);
+			rc = ebitmap_init_range(&tmp, 0, max - 1);
 			if (rc != SEPOL_OK) {
 				cil_log(CIL_INFO, "Failed to expand 'all' operator\n");
 				ebitmap_destroy(&tmp);
@@ -1328,19 +1320,15 @@ static int __cil_expr_to_bitmap(struct cil_list *expr, ebitmap_t *out, int max,
 			}
 		} else if (op == CIL_RANGE) {
 			if (flavor == CIL_CAT) {
-				ebitmap_init(&tmp);
 				rc = __cil_cat_expr_range_to_bitmap_helper(curr->next, curr->next->next, &tmp);
 				if (rc != SEPOL_OK) {
 					cil_log(CIL_INFO, "Failed to expand category range\n");
-					ebitmap_destroy(&tmp);
 					goto exit;
 				}
 			} else if (flavor == CIL_PERMISSIONX) {
-				ebitmap_init(&tmp);
 				rc = __cil_permissionx_expr_range_to_bitmap_helper(curr->next, curr->next->next, &tmp);
 				if (rc != SEPOL_OK) {
 					cil_log(CIL_INFO, "Failed to expand category range\n");
-					ebitmap_destroy(&tmp);
 					goto exit;
 				}
 			} else {
Signature · 1 line
2.36.1
Acked-by on v1 3/7
#4 lore raw

Re: [PATCH 3/7] libsepol/cil: use ebitmap_init_range

Quoted 6 lines · Christian Göttsche

Especially in the case of __cil_permissionx_expr_range_to_bitmap_helper() it substitutes hundreds of thousand of calls to ebitmap_set_bit() during semodule(8) on a policy widely using extended permissions.

Quoted 92 lines
---
 libsepol/cil/src/cil_post.c | 30 +++++++++---------------------
 1 file changed, 9 insertions(+), 21 deletions(-)
libsepol/cil/src/cil_post.c +9 -22
index 714ce227..6e95225f 100644
@@ -1191,7 +1191,6 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, struc
        struct cil_tree_node *n2 = d2->nodes->head->data;
        struct cil_cat *c1 = (struct cil_cat *)d1;
        struct cil_cat *c2 = (struct cil_cat *)d2;
-       int i;
 
        if (n1->flavor == CIL_CATSET || n2->flavor == CIL_CATSET) {
                cil_log(CIL_ERR, "Category sets cannont be used in a category range\n");
@@ -1213,12 +1212,10 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, struc
                goto exit;
        }
 
-       for (i = c1->value; i <= c2->value; i++) {
-               if (ebitmap_set_bit(bitmap, i, 1)) {
-                       cil_log(CIL_ERR, "Failed to set cat bit\n");
-                       ebitmap_destroy(bitmap);
-                       goto exit;
-               }
+       if (ebitmap_init_range(bitmap, c1->value, c2->value)) {
+               cil_log(CIL_ERR, "Failed to set cat bit\n");
+               ebitmap_destroy(bitmap);
+               goto exit;
        }
 
        return SEPOL_OK;
@@ -1234,7 +1231,6 @@ static int __cil_permissionx_expr_range_to_bitmap_helper(struct cil_list_item *i
        char *p2 = i2->data;
        uint16_t v1;
        uint16_t v2;
-       uint32_t i;
 
        rc = __cil_permx_str_to_int(p1, &v1);
        if (rc != SEPOL_OK) {
@@ -1246,12 +1242,10 @@ static int __cil_permissionx_expr_range_to_bitmap_helper(struct cil_list_item *i
                goto exit;
        }
 
-       for (i = v1; i <= v2; i++) {
-               if (ebitmap_set_bit(bitmap, i, 1)) {
-                       cil_log(CIL_ERR, "Failed to set permissionx bit\n");
-                       ebitmap_destroy(bitmap);
-                       goto exit;
-               }
+       if (ebitmap_init_range(bitmap, v1, v2)) {
+               cil_log(CIL_ERR, "Failed to set permissionx bits\n");
+               ebitmap_destroy(bitmap);
+               goto exit;
        }
 
        return SEPOL_OK;
@@ -1318,9 +1312,7 @@ static int __cil_expr_to_bitmap(struct cil_list *expr, ebitmap_t *out, int max,
                enum cil_flavor op = (enum cil_flavor)(uintptr_t)curr->data;
 
                if (op == CIL_ALL) {
-                       ebitmap_init(&b1); /* all zeros */
-                       rc = ebitmap_not(&tmp, &b1, max);
-                       ebitmap_destroy(&b1);
+                       rc = ebitmap_init_range(&tmp, 0, max - 1);
                        if (rc != SEPOL_OK) {
                                cil_log(CIL_INFO, "Failed to expand 'all' operator\n");
                                ebitmap_destroy(&tmp);
@@ -1328,19 +1320,15 @@ static int __cil_expr_to_bitmap(struct cil_list *expr, ebitmap_t *out, int max,
                        }
                } else if (op == CIL_RANGE) {
                        if (flavor == CIL_CAT) {
-                               ebitmap_init(&tmp);
                                rc = __cil_cat_expr_range_to_bitmap_helper(curr->next, curr->next->next, &tmp);
                                if (rc != SEPOL_OK) {
                                        cil_log(CIL_INFO, "Failed to expand category range\n");
-                                       ebitmap_destroy(&tmp);
                                        goto exit;
                                }
                        } else if (flavor == CIL_PERMISSIONX) {
-                               ebitmap_init(&tmp);
                                rc = __cil_permissionx_expr_range_to_bitmap_helper(curr->next, curr->next->next, &tmp);
                                if (rc != SEPOL_OK) {
                                        cil_log(CIL_INFO, "Failed to expand category range\n");
-                                       ebitmap_destroy(&tmp);
                                        goto exit;
                                }
                        } else {
--

2.36.1

#5 lore raw

PATCH 4/7 libsepol: optimize ebitmap_not

In reply to Christian Göttsche

Iterate on nodes instead of single bits to save node resolution for each single bit.

---
 libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 42 insertions(+), 6 deletions(-)
libsepol/src/ebitmap.c +42 -6
index fb20e994..6a63e559 100644
@@ -101,14 +101,50 @@ int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 
 int ebitmap_not(ebitmap_t *dst, const ebitmap_t *e1, unsigned int maxbit)
 {
-	unsigned int i;
+	const ebitmap_node_t *n;
+	ebitmap_node_t *new, *prev = NULL;
+	uint32_t startbit, cur_startbit;
+	MAPTYPE map;
+
 	ebitmap_init(dst);
-	for (i=0; i < maxbit; i++) {
-		int val = ebitmap_get_bit(e1, i);
-		int rc = ebitmap_set_bit(dst, i, !val);
-		if (rc < 0)
-			return rc;
+
+	n = e1->node;
+	for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
+		if (n && n->startbit == cur_startbit) {
+			startbit = n->startbit;
+			map = ~n->map;
+
+			n = n->next;
+		} else {
+			startbit = cur_startbit;
+			map = ~((MAPTYPE) 0);
+		}
+
+		if (maxbit - cur_startbit < MAPSIZE)
+			map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;
+
+		if (map != 0) {
+			new = malloc(sizeof(ebitmap_node_t));
+			if (!new) {
+				ebitmap_destroy(dst);
+				return -ENOMEM;
+			}
+
+			new->startbit = startbit;
+			new->map = map;
+			new->next = NULL;
+
+			if (prev)
+				prev->next = new;
+			else
+				dst->node = new;
+			prev = new;
+		}
 	}
+
+	if (prev)
+		dst->highbit = prev->startbit + MAPSIZE;
+
 	return 0;
 }
 
Signature · 1 line
2.36.1
Acked-by on v1 4/7
#6 lore raw

Re: [PATCH 4/7] libsepol: optimize ebitmap_not

Quoted 5 lines · Christian Göttsche

Iterate on nodes instead of single bits to save node resolution for each single bit.

Quoted 68 lines
---
 libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 42 insertions(+), 6 deletions(-)
libsepol/src/ebitmap.c +42 -7
index fb20e994..6a63e559 100644
@@ -101,14 +101,50 @@ int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 
 int ebitmap_not(ebitmap_t *dst, const ebitmap_t *e1, unsigned int maxbit)
 {
-       unsigned int i;
+       const ebitmap_node_t *n;
+       ebitmap_node_t *new, *prev = NULL;
+       uint32_t startbit, cur_startbit;
+       MAPTYPE map;
+
        ebitmap_init(dst);
-       for (i=0; i < maxbit; i++) {
-               int val = ebitmap_get_bit(e1, i);
-               int rc = ebitmap_set_bit(dst, i, !val);
-               if (rc < 0)
-                       return rc;
+
+       n = e1->node;
+       for (cur_startbit = 0; cur_startbit < maxbit; cur_startbit += MAPSIZE) {
+               if (n && n->startbit == cur_startbit) {
+                       startbit = n->startbit;
+                       map = ~n->map;
+
+                       n = n->next;
+               } else {
+                       startbit = cur_startbit;
+                       map = ~((MAPTYPE) 0);
+               }
+
+               if (maxbit - cur_startbit < MAPSIZE)
+                       map &= (((MAPTYPE)1) << (maxbit - cur_startbit)) - 1;
+
+               if (map != 0) {
+                       new = malloc(sizeof(ebitmap_node_t));
+                       if (!new) {
+                               ebitmap_destroy(dst);
+                               return -ENOMEM;
+                       }
+
+                       new->startbit = startbit;
+                       new->map = map;
+                       new->next = NULL;
+
+                       if (prev)
+                               prev->next = new;
+                       else
+                               dst->node = new;
+                       prev = new;
+               }
        }
+
+       if (prev)
+               dst->highbit = prev->startbit + MAPSIZE;
+
        return 0;
 }
 
--

2.36.1

#7 lore raw

PATCH 5/7 libsepol: optimize ebitmap_and

In reply to Christian Göttsche

Iterate on nodes instead of single bits to save node resolution for each single bit.

---
 libsepol/src/ebitmap.c | 42 +++++++++++++++++++++++++++++++++++-------
 1 file changed, 35 insertions(+), 7 deletions(-)
libsepol/src/ebitmap.c +35 -7
index 6a63e559..c3d706e9 100644
@@ -74,15 +74,43 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
 
 int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 {
-	unsigned int i, length = min(ebitmap_length(e1), ebitmap_length(e2));
+	const ebitmap_node_t *n1, *n2;
+	ebitmap_node_t *new, *prev = NULL;
+
 	ebitmap_init(dst);
-	for (i=0; i < length; i++) {
-		if (ebitmap_get_bit(e1, i) && ebitmap_get_bit(e2, i)) {
-			int rc = ebitmap_set_bit(dst, i, 1);
-			if (rc < 0)
-				return rc;
-		}
+
+	n1 = e1->node;
+	n2 = e2->node;
+	while (n1 && n2) {
+		if (n1->startbit == n2->startbit) {
+			if (n1->map & n2->map) {
+				new = malloc(sizeof(ebitmap_node_t));
+				if (!new) {
+					ebitmap_destroy(dst);
+					return -ENOMEM;
+				}
+				new->startbit = n1->startbit;
+				new->map = n1->map & n2->map;
+				new->next = NULL;
+
+				if (prev)
+					prev->next = new;
+				else
+					dst->node = new;
+				prev = new;
+			}
+
+			n1 = n1->next;
+			n2 = n2->next;
+		} else if (n1->startbit > n2->startbit)
+			n2 = n2->next;
+		else
+			n1 = n1->next;
 	}
+
+	if (prev)
+		dst->highbit = prev->startbit + MAPSIZE;
+
 	return 0;
 }
 
Signature · 1 line
2.36.1
#8 lore raw

Re: [PATCH 5/7] libsepol: optimize ebitmap_and

Quoted 46 lines · Christian Göttsche

Iterate on nodes instead of single bits to save node resolution for each single bit.

---
 libsepol/src/ebitmap.c | 42 +++++++++++++++++++++++++++++++++++-------
 1 file changed, 35 insertions(+), 7 deletions(-)
libsepol/src/ebitmap.c +21 -7
index 6a63e559..c3d706e9 100644
@@ -74,15 +74,43 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
 
 int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 {
-       unsigned int i, length = min(ebitmap_length(e1), ebitmap_length(e2));
+       const ebitmap_node_t *n1, *n2;
+       ebitmap_node_t *new, *prev = NULL;
+
        ebitmap_init(dst);
-       for (i=0; i < length; i++) {
-               if (ebitmap_get_bit(e1, i) && ebitmap_get_bit(e2, i)) {
-                       int rc = ebitmap_set_bit(dst, i, 1);
-                       if (rc < 0)
-                               return rc;
-               }
+
+       n1 = e1->node;
+       n2 = e2->node;
+       while (n1 && n2) {
+               if (n1->startbit == n2->startbit) {
+                       if (n1->map & n2->map) {
+                               new = malloc(sizeof(ebitmap_node_t));
+                               if (!new) {
+                                       ebitmap_destroy(dst);
+                                       return -ENOMEM;
+                               }
+                               new->startbit = n1->startbit;
+                               new->map = n1->map & n2->map;
+                               new->next = NULL;
+
+                               if (prev)
+                                       prev->next = new;
+                               else

libsepol/src/ebitmap.c int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1) · line 108

Quoted 10 lines
libsepol/src/ebitmap.c +10 -0
+                                       dst->node = new;
+                               prev = new;
+                       }
+
+                       n1 = n1->next;
+                       n2 = n2->next;
+               } else if (n1->startbit > n2->startbit)
+                       n2 = n2->next;
+               else
+                       n1 = n1->next;

I would like to see braces around the last two clauses.

Thanks,
Jim

Quoted 11 lines
libsepol/src/ebitmap.c +4 -1
        }
+
+       if (prev)
+               dst->highbit = prev->startbit + MAPSIZE;
+
        return 0;
 }
 
--

2.36.1

#9 lore raw

PATCH 6/7 libsepol: optimize ebitmap_xor

In reply to Christian Göttsche

Iterate on nodes instead of single bits to save node resolution for each single bit.

---
 libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 43 insertions(+), 6 deletions(-)
libsepol/src/ebitmap.c +43 -6
index c3d706e9..e0541abb 100644
@@ -116,14 +116,51 @@ int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 
 int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 {
-	unsigned int i, length = max(ebitmap_length(e1), ebitmap_length(e2));
+	const ebitmap_node_t *n1, *n2;
+	ebitmap_node_t *new, *prev = NULL;
+	uint32_t startbit;
+	MAPTYPE map;
+
 	ebitmap_init(dst);
-	for (i=0; i < length; i++) {
-		int val = ebitmap_get_bit(e1, i) ^ ebitmap_get_bit(e2, i);
-		int rc = ebitmap_set_bit(dst, i, val);
-		if (rc < 0)
-			return rc;
+
+	n1 = e1->node;
+	n2 = e2->node;
+	while (n1 || n2) {
+		if (n1 && n2 && n1->startbit == n2->startbit) {
+			startbit = n1->startbit;
+			map = n1->map ^ n2->map;
+			n1 = n1->next;
+			n2 = n2->next;
+		} else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
+			startbit = n1->startbit;
+			map = n1->map;
+			n1 = n1->next;
+		} else {
+			startbit = n2->startbit;
+			map = n2->map;
+			n2 = n2->next;
+		}
+
+		if (map != 0) {
+			new = malloc(sizeof(ebitmap_node_t));
+			if (!new) {
+				ebitmap_destroy(dst);
+				return -ENOMEM;
+			}
+			new->startbit = startbit;
+			new->map = map;
+			new->next = NULL;
+			if (prev)
+				prev->next = new;
+			else
+				dst->node = new;
+			prev = new;
+		}
 	}
+
+	if (prev)
+		dst->highbit = prev->startbit + MAPSIZE;
+
 	return 0;
 }
 
Signature · 1 line
2.36.1
Acked-by on v1 6/7
#10 lore raw

Re: [PATCH 6/7] libsepol: optimize ebitmap_xor

Quoted 5 lines · Christian Göttsche

Iterate on nodes instead of single bits to save node resolution for each single bit.

Quoted 69 lines
---
 libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 43 insertions(+), 6 deletions(-)
libsepol/src/ebitmap.c +43 -7
index c3d706e9..e0541abb 100644
@@ -116,14 +116,51 @@ int ebitmap_and(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 
 int ebitmap_xor(ebitmap_t *dst, const ebitmap_t *e1, const ebitmap_t *e2)
 {
-       unsigned int i, length = max(ebitmap_length(e1), ebitmap_length(e2));
+       const ebitmap_node_t *n1, *n2;
+       ebitmap_node_t *new, *prev = NULL;
+       uint32_t startbit;
+       MAPTYPE map;
+
        ebitmap_init(dst);
-       for (i=0; i < length; i++) {
-               int val = ebitmap_get_bit(e1, i) ^ ebitmap_get_bit(e2, i);
-               int rc = ebitmap_set_bit(dst, i, val);
-               if (rc < 0)
-                       return rc;
+
+       n1 = e1->node;
+       n2 = e2->node;
+       while (n1 || n2) {
+               if (n1 && n2 && n1->startbit == n2->startbit) {
+                       startbit = n1->startbit;
+                       map = n1->map ^ n2->map;
+                       n1 = n1->next;
+                       n2 = n2->next;
+               } else if (!n2 || (n1 && n1->startbit < n2->startbit)) {
+                       startbit = n1->startbit;
+                       map = n1->map;
+                       n1 = n1->next;
+               } else {
+                       startbit = n2->startbit;
+                       map = n2->map;
+                       n2 = n2->next;
+               }
+
+               if (map != 0) {
+                       new = malloc(sizeof(ebitmap_node_t));
+                       if (!new) {
+                               ebitmap_destroy(dst);
+                               return -ENOMEM;
+                       }
+                       new->startbit = startbit;
+                       new->map = map;
+                       new->next = NULL;
+                       if (prev)
+                               prev->next = new;
+                       else
+                               dst->node = new;
+                       prev = new;
+               }
        }
+
+       if (prev)
+               dst->highbit = prev->startbit + MAPSIZE;
+
        return 0;
 }
 
--

2.36.1

#11 lore raw

PATCH 7/7 libsepol: skip superfluous memset calls in ebitmap operations

In reply to Christian Göttsche

The three members of struct ebitmap_node are all unconditionally initialized. Hinder compilers to optimize malloc() and memset() into calloc(), which might be slightly slower. Especially affects ebitmap_or().

---
 libsepol/src/ebitmap.c | 3 ---
 1 file changed, 3 deletions(-)
libsepol/src/ebitmap.c +0 -3
index e0541abb..d0f7daba 100644
@@ -31,7 +31,6 @@ int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
 			ebitmap_destroy(dst);
 			return -ENOMEM;
 		}
-		memset(new, 0, sizeof(ebitmap_node_t));
 		if (n1 && n2 && n1->startbit == n2->startbit) {
 			new->startbit = n1->startbit;
 			new->map = n1->map | n2->map;
@@ -289,7 +288,6 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
 			ebitmap_destroy(dst);
 			return -ENOMEM;
 		}
-		memset(new, 0, sizeof(ebitmap_node_t));
 		new->startbit = n->startbit;
 		new->map = n->map;
 		new->next = 0;
@@ -429,7 +427,6 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
 	new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
 	if (!new)
 		return -ENOMEM;
-	memset(new, 0, sizeof(ebitmap_node_t));
 
 	new->startbit = startbit;
 	new->map = (MAPBIT << (bit - new->startbit));
Signature · 1 line
2.36.1
Acked-by on v1 7/7
#12 lore raw

Re: [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations

Quoted 7 lines · Christian Göttsche

The three members of struct ebitmap_node are all unconditionally initialized. Hinder compilers to optimize malloc() and memset() into calloc(), which might be slightly slower. Especially affects ebitmap_or().

Quoted 35 lines
---
 libsepol/src/ebitmap.c | 3 ---
 1 file changed, 3 deletions(-)
libsepol/src/ebitmap.c +0 -4
index e0541abb..d0f7daba 100644
@@ -31,7 +31,6 @@ int ebitmap_or(ebitmap_t * dst, const ebitmap_t * e1, const ebitmap_t * e2)
                        ebitmap_destroy(dst);
                        return -ENOMEM;
                }
-               memset(new, 0, sizeof(ebitmap_node_t));
                if (n1 && n2 && n1->startbit == n2->startbit) {
                        new->startbit = n1->startbit;
                        new->map = n1->map | n2->map;
@@ -289,7 +288,6 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
                        ebitmap_destroy(dst);
                        return -ENOMEM;
                }
-               memset(new, 0, sizeof(ebitmap_node_t));
                new->startbit = n->startbit;
                new->map = n->map;
                new->next = 0;
@@ -429,7 +427,6 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
        new = (ebitmap_node_t *) malloc(sizeof(ebitmap_node_t));
        if (!new)
                return -ENOMEM;
-       memset(new, 0, sizeof(ebitmap_node_t));
 
        new->startbit = startbit;
        new->map = (MAPBIT << (bit - new->startbit));
--

2.36.1

#13 lore raw
In reply to Christian Göttsche
Quoted 68 lines · Christian Göttsche

Preparation for several ebitmap related optimizations.

---
 libsepol/tests/libsepol-tests.c |   2 +
 libsepol/tests/test-ebitmap.c   | 711 ++++++++++++++++++++++++++++++++
 libsepol/tests/test-ebitmap.h   |  10 +
 3 files changed, 723 insertions(+)
 create mode 100644 libsepol/tests/test-ebitmap.c
 create mode 100644 libsepol/tests/test-ebitmap.h
libsepol/tests/libsepol-tests.c +2 -0
index dc8fd5ce..5ae6bedc 100644
@@ -19,6 +19,7 @@
  */
 
 #include "test-cond.h"
+#include "test-ebitmap.h"
 #include "test-linker.h"
 #include "test-expander.h"
 #include "test-deps.h"
@@ -64,6 +65,7 @@ static bool do_tests(int interactive, int verbose)
        if (CUE_SUCCESS != CU_initialize_registry())
                return CU_get_error();
 
+       DECLARE_SUITE(ebitmap);
        DECLARE_SUITE(cond);
        DECLARE_SUITE(linker);
        DECLARE_SUITE(expander);
libsepol/tests/test-ebitmap.c new file +30 -0
new file mode 100644
index 00000000..a21f18c0
@@ -0,0 +1,711 @@
+#include "test-ebitmap.h"
+
+#include <stdlib.h>
+#include <time.h>
+
+#include <sepol/debug.h>
+#include <sepol/policydb/ebitmap.h>
+
+#define RANDOM_ROUNDS 10
+
+
+static int ebitmap_init_random(ebitmap_t *e, unsigned int length, int set_chance)
+{
+       unsigned int i;
+       int rc;
+
+       if (set_chance <= 0 || set_chance > 100)
+               return -EINVAL;
+
+       ebitmap_init(e);
+
+       for (i = 0; i < length; i++) {
+               if ((random() % 100) < set_chance) {
+                       rc = ebitmap_set_bit(e, i, 1);
+                       if (rc)
+                               return rc;
+               }
+       }
+
+       return 0;

libsepol/tests/test-ebitmap.c line 40

Quoted 10 lines
libsepol/tests/test-ebitmap.c new file +10 -0
+}
+
+static void test_ebitmap_init_destroy(void)
+{
+       ebitmap_t e;
+
+       ebitmap_init(&e);
+       ebitmap_init(&e);
+       ebitmap_init(&e);
+

I am not sure what we are testing here. ebitmap_init() is just doing a memset.

libsepol/tests/test-ebitmap.c line 47

Quoted 7 lines
libsepol/tests/test-ebitmap.c new file +7 -0
+       CU_ASSERT(ebitmap_is_empty(&e));
+       CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
+
+       ebitmap_destroy(&e);
+       ebitmap_destroy(&e);
+       ebitmap_destroy(&e);
+

I don't know what we are testing here either.

Quoted 11 lines
libsepol/tests/test-ebitmap.c new file +11 -0
+       CU_ASSERT(ebitmap_is_empty(&e));
+       CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
+}
+
+static void test_ebitmap_cmp(void)
+{
+       ebitmap_t e1, e2;
+
+       ebitmap_init(&e1);
+       ebitmap_init(&e2);
+

libsepol/tests/test-ebitmap.c line 68

Quoted 10 lines
libsepol/tests/test-ebitmap.c new file +10 -0
+       CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+       CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 10, 1), 0);
+
+       CU_ASSERT(ebitmap_cmp(&e1, &e2));
+

For all the tests we should test with values that will require more that one ebitmap_node_t and test bits that are going to be at the boundaries of the nodes (l0, 63, 64, 127, ...) and some bits in between.

Quoted 29 lines
libsepol/tests/test-ebitmap.c new file +29 -0
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_set_and_get(void)
+{
+       ebitmap_t e;
+
+       ebitmap_init(&e);
+
+       CU_ASSERT(ebitmap_is_empty(&e));
+       CU_ASSERT_TRUE(ebitmap_is_empty(&e));
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, UINT32_MAX, 1), -EINVAL);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 1), 0);
+       CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 10);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 1);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 1), 0);
+       CU_ASSERT_FALSE(ebitmap_is_empty(&e));

libsepol/tests/test-ebitmap.c line 107

Quoted 10 lines
libsepol/tests/test-ebitmap.c new file +10 -0
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 1);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 1), 0);
+       CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 1);
+

This is at least using more than one ebitmap_node_t, but I would still like to make sure we are handling the edge cases properly.

Quoted 240 lines
libsepol/tests/test-ebitmap.c new file +240 -0
+       {
+               ebitmap_node_t *n;
+               unsigned int bit;
+
+               ebitmap_for_each_positive_bit(&e, n, bit) {
+                       CU_ASSERT(bit == 10 || bit == 50 || bit == 100);
+               }
+       }
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 0), 0);
+       CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 50);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
+       CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 50);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 0), 0);
+       CU_ASSERT_TRUE(ebitmap_is_empty(&e));
+       CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+       CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+       CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 0);
+
+       ebitmap_destroy(&e);
+}
+
+static void test_ebitmap_or(void)
+{
+       ebitmap_t e1, e2, e3, e4;
+
+       ebitmap_init(&e1);
+       ebitmap_init(&e2);
+       ebitmap_init(&e3);
+       ebitmap_init(&e4);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e1), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_or(&dst, &e2, &e2), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e2), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e3), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e4), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_or(&dst, &e4, &e4), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       ebitmap_destroy(&e4);
+       ebitmap_destroy(&e3);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_and(void)
+{
+       ebitmap_t e1, e2, e12, e3, e4;
+
+       ebitmap_init(&e1);
+       ebitmap_init(&e2);
+       ebitmap_init(&e12);
+       ebitmap_init(&e3);
+       ebitmap_init(&e4);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 101, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e1), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e2), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e2), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e12));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e3), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e3), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e3), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e4, &e4), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e4), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       ebitmap_destroy(&e4);
+       ebitmap_destroy(&e3);
+       ebitmap_destroy(&e12);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_xor(void)
+{
+       ebitmap_t e1, e2, e3, e4;
+
+       ebitmap_init(&e1);
+       ebitmap_init(&e2);
+       ebitmap_init(&e3);
+       ebitmap_init(&e4);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1, 1), 0);

libsepol/tests/test-ebitmap.c line 357

Quoted 10 lines
libsepol/tests/test-ebitmap.c new file +10 -0
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 3, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 5, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 6, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 9, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+

I would like to see bits > 64 being tested to test the case with more than one ebitmap_node_t.

Quoted 75 lines
libsepol/tests/test-ebitmap.c new file +75 -0
+       {
+               ebitmap_t dst1, dst2;
+
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst1, &e1, &e1), 0);
+               CU_ASSERT(ebitmap_cmp(&dst1, &e4));
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst2, &dst1, &e1), 0);
+               CU_ASSERT(ebitmap_cmp(&dst2, &e1));
+
+               ebitmap_destroy(&dst2);
+               ebitmap_destroy(&dst1);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e2), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e3, &e3), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e4, &e4), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e1, &e2), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e4), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+               ebitmap_destroy(&dst);
+       }
+
+       ebitmap_destroy(&e4);
+       ebitmap_destroy(&e3);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_not(void)
+{
+       ebitmap_t e1, e2, e3, e4;
+
+       ebitmap_init(&e1);
+       ebitmap_init(&e2);
+       ebitmap_init(&e3);
+       ebitmap_init(&e4);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 0, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);

libsepol/tests/test-ebitmap.c line 442

Quoted 10 lines
libsepol/tests/test-ebitmap.c new file +10 -0
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 2, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 4, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 7, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 8, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
+

Same here.

Tests are a nice and needed addition.

Thanks,
Jim

Quoted 288 lines
libsepol/tests/test-ebitmap.c new file +269 -0
+       {
+               ebitmap_t dst1, dst2;
+
+               CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e3, 10), 0);
+               CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst1), 9);
+               CU_ASSERT_EQUAL(ebitmap_cardinality(&dst1), 10);
+
+               CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 10), 0);
+               CU_ASSERT(ebitmap_cmp(&dst2, &e3));
+
+               ebitmap_destroy(&dst2);
+               ebitmap_destroy(&dst1);
+       }
+
+       {
+               ebitmap_t dst1, dst2;
+
+               CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e1, 11), 0);
+               CU_ASSERT(ebitmap_cmp(&dst1, &e2));
+               CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 11), 0);
+               CU_ASSERT(ebitmap_cmp(&dst2, &e1));
+
+               ebitmap_destroy(&dst2);
+               ebitmap_destroy(&dst1);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 8), 0);
+               CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 7);
+               CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 5);
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 12), 0);
+               CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 11);
+               CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 8);
+
+               ebitmap_destroy(&dst);
+       }
+
+       ebitmap_destroy(&e3);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_andnot(void)
+{
+       ebitmap_t e1, e2, e12, e3, e4;
+
+       ebitmap_init(&e1);
+       ebitmap_init(&e2);
+       ebitmap_init(&e12);
+       ebitmap_init(&e3);
+       ebitmap_init(&e4);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 1013, 1), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+       CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e1, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e2, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e2, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e12));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e3, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e3, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e12, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e4, &e4, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+               ebitmap_destroy(&dst);
+       }
+
+       {
+               ebitmap_t dst;
+
+               CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e4, 1024), 0);
+               CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+               ebitmap_destroy(&dst);
+       }
+
+       ebitmap_destroy(&e4);
+       ebitmap_destroy(&e3);
+       ebitmap_destroy(&e12);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap__random_impl(unsigned int length, int set_chance)
+{
+       ebitmap_t e1, e2, dst_cpy, dst_or, dst_and, dst_xor1, dst_xor2, dst_not1, dst_not2, dst_andnot;
+       unsigned int i;
+
+       CU_ASSERT_EQUAL(ebitmap_init_random(&e1, length, set_chance), 0);
+       CU_ASSERT_EQUAL(ebitmap_init_random(&e2, length, set_chance), 0);
+
+       CU_ASSERT_EQUAL(ebitmap_cpy(&dst_cpy, &e1), 0);
+       CU_ASSERT(ebitmap_cmp(&dst_cpy, &e1));
+
+       CU_ASSERT_EQUAL(ebitmap_or(&dst_or, &e1, &e2), 0);
+       for (i = 0; i < length; i++)
+               CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_or, i), ebitmap_get_bit(&e1, i) | ebitmap_get_bit(&e2, i));
+
+       CU_ASSERT_EQUAL(ebitmap_and(&dst_and, &e1, &e2), 0);
+       for (i = 0; i < length; i++)
+               CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_and, i), ebitmap_get_bit(&e1, i) & ebitmap_get_bit(&e2, i));
+
+       CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor1, &e1, &e2), 0);
+       for (i = 0; i < length; i++)
+               CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_xor1, i), ebitmap_get_bit(&e1, i) ^ ebitmap_get_bit(&e2, i));
+       CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor2, &dst_xor1, &e2), 0);
+       CU_ASSERT(ebitmap_cmp(&dst_xor2, &e1));
+
+       CU_ASSERT_EQUAL(ebitmap_not(&dst_not1, &e1, length), 0);
+       for (i = 0; i < length; i++)
+               CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_not1, i), !ebitmap_get_bit(&e1, i));
+       CU_ASSERT_EQUAL(ebitmap_not(&dst_not2, &dst_not1, length), 0);
+       CU_ASSERT(ebitmap_cmp(&dst_not2, &e1));
+
+       CU_ASSERT_EQUAL(ebitmap_andnot(&dst_andnot, &e1, &e2, length), 0);
+       for (i = 0; i < length; i++)
+               CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_andnot, i), ebitmap_get_bit(&e1, i) & !ebitmap_get_bit(&e2, i));
+
+       ebitmap_destroy(&dst_andnot);
+       ebitmap_destroy(&dst_not2);
+       ebitmap_destroy(&dst_not1);
+       ebitmap_destroy(&dst_xor2);
+       ebitmap_destroy(&dst_xor1);
+       ebitmap_destroy(&dst_and);
+       ebitmap_destroy(&dst_or);
+       ebitmap_destroy(&dst_cpy);
+       ebitmap_destroy(&e2);
+       ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap__random(void)
+{
+       unsigned int i;
+
+       for (i = 0; i < RANDOM_ROUNDS; i++)
+               test_ebitmap__random_impl(5, 10);
+
+       for (i = 0; i < RANDOM_ROUNDS; i++)
+               test_ebitmap__random_impl(5, 90);
+
+       for (i = 0; i < RANDOM_ROUNDS; i++)
+               test_ebitmap__random_impl(1024, 50);
+
+       for (i = 0; i < RANDOM_ROUNDS; i++)
+               test_ebitmap__random_impl(8000, 5);
+
+       for (i = 0; i < RANDOM_ROUNDS; i++)
+               test_ebitmap__random_impl(8000, 95);
+}
+
+/*
+ * External hooks
+ */
+
+int ebitmap_test_init(void)
+{
+       srandom(time(NULL));
+
+       /* silence ebitmap_set_bit() failure message */
+       sepol_debug(0);
+
+       return 0;
+}
+
+int ebitmap_test_cleanup(void)
+{
+       return 0;
+}
+
+#define ADD_TEST(name) \
+       do { \
+               if (NULL == CU_add_test(suite, #name, test_##name)) { \
+                       return CU_get_error(); \
+               } \
+       } while (0)
+
+int ebitmap_add_tests(CU_pSuite suite)
+{
+       ADD_TEST(ebitmap_init_destroy);
+       ADD_TEST(ebitmap_cmp);
+       ADD_TEST(ebitmap_set_and_get);
+       ADD_TEST(ebitmap_or);
+       ADD_TEST(ebitmap_and);
+       ADD_TEST(ebitmap_xor);
+       ADD_TEST(ebitmap_not);
+       ADD_TEST(ebitmap_andnot);
+       ADD_TEST(ebitmap__random);
+       return 0;
+}
libsepol/tests/test-ebitmap.h new file +10 -1
new file mode 100644
index 00000000..952a0421
@@ -0,0 +1,10 @@
+#ifndef TEST_EBITMAP_H__
+#define TEST_EBITMAP_H__
+
+#include <CUnit/Basic.h>
+
+int ebitmap_test_init(void);
+int ebitmap_test_cleanup(void);
+int ebitmap_add_tests(CU_pSuite suite);
+
+#endif  /* TEST_EBITMAP_H__ */
--

2.36.1