libsepol/tests: add ebitmap tests
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
@@ -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
@@ -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
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
@@ -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
@@ -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
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 iteratingebitmap_set_bit().Signed-off-by Christian Göttsche <[email protected]>--- 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@@ -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@@ -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@@ -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
PATCH 3/7 libsepol/cil: use ebitmap_init_range
In reply to Christian GöttscheEspecially 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
@@ -1191,7 +1191,6 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, strucstruct 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 *ichar *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
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 toebitmap_set_bit()during semodule(8) on a policy widely using extended permissions.Signed-off-by Christian Göttsche <[email protected]>
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@@ -1191,7 +1191,6 @@ static int __cil_cat_expr_range_to_bitmap_helper(struct cil_list_item *i1, strucstruct 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 *ichar *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
PATCH 4/7 libsepol: optimize ebitmap_not
In reply to Christian GöttscheIterate 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
@@ -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
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.
Signed-off-by Christian Göttsche <[email protected]>
Quoted 68 lines
--- libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 42 insertions(+), 6 deletions(-)libsepol/src/ebitmap.c +42
-7@@ -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
PATCH 5/7 libsepol: optimize ebitmap_and
In reply to Christian GöttscheIterate 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
@@ -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
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.
Signed-off-by Christian Göttsche <[email protected]>--- libsepol/src/ebitmap.c | 42 +++++++++++++++++++++++++++++++++++------- 1 file changed, 35 insertions(+), 7 deletions(-)libsepol/src/ebitmap.c +21
-7@@ -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
PATCH 6/7 libsepol: optimize ebitmap_xor
In reply to Christian GöttscheIterate 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
@@ -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
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.
Signed-off-by Christian Göttsche <[email protected]>
Quoted 69 lines
--- libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 43 insertions(+), 6 deletions(-)libsepol/src/ebitmap.c +43
-7@@ -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
PATCH 7/7 libsepol: skip superfluous memset calls in ebitmap operations
In reply to Christian GöttscheThe 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
@@ -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
Re: [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations
Quoted 7 lines · Christian Göttsche
The three members of struct
ebitmap_nodeare all unconditionally initialized. Hinder compilers to optimizemalloc()andmemset()intocalloc(), which might be slightly slower. Especially affectsebitmap_or().Signed-off-by Christian Göttsche <[email protected]>
Quoted 35 lines
--- libsepol/src/ebitmap.c | 3 --- 1 file changed, 3 deletions(-)libsepol/src/ebitmap.c +0
-4@@ -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
Quoted 68 lines · Christian Göttsche
Preparation for several ebitmap related optimizations.
Signed-off-by Christian Göttsche <[email protected]>--- 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.hlibsepol/tests/libsepol-tests.c +2
-0@@ -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@@ -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@@ -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