* [PATCH 1/7] libsepol/tests: add ebitmap tests @ 2022-07-12 16:08 Christian Göttsche 2022-07-12 16:08 ` [PATCH 2/7] libsepol: add ebitmap_init_range Christian Göttsche ` (6 more replies) 0 siblings, 7 replies; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux Preparation for several ebitmap related optimizations. Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- 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 diff --git a/libsepol/tests/libsepol-tests.c b/libsepol/tests/libsepol-tests.c index dc8fd5ce..5ae6bedc 100644 --- a/libsepol/tests/libsepol-tests.c +++ b/libsepol/tests/libsepol-tests.c @@ -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); diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c new file mode 100644 index 00000000..a21f18c0 --- /dev/null +++ b/libsepol/tests/test-ebitmap.c @@ -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; +} + +static void test_ebitmap_init_destroy(void) +{ + ebitmap_t e; + + ebitmap_init(&e); + ebitmap_init(&e); + ebitmap_init(&e); + + CU_ASSERT(ebitmap_is_empty(&e)); + CU_ASSERT_PTR_NULL(ebitmap_startnode(&e)); + + ebitmap_destroy(&e); + ebitmap_destroy(&e); + ebitmap_destroy(&e); + + 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); + + 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)); + + 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)); + 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); + + { + 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); + 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); + + { + 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); + 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); + + { + 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; +} diff --git a/libsepol/tests/test-ebitmap.h b/libsepol/tests/test-ebitmap.h new file mode 100644 index 00000000..952a0421 --- /dev/null +++ b/libsepol/tests/test-ebitmap.h @@ -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 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH 2/7] libsepol: add ebitmap_init_range 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche @ 2022-07-12 16:08 ` Christian Göttsche 2022-07-18 20:43 ` James Carter 2022-07-12 16:08 ` [PATCH 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche ` (5 subsequent siblings) 6 siblings, 1 reply; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux 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(). Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- libsepol/include/sepol/policydb/ebitmap.h | 1 + libsepol/src/ebitmap.c | 49 +++++++++++++++++++++++ libsepol/tests/test-ebitmap.c | 32 +++++++++++++++ 3 files changed, 82 insertions(+) diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h index 81d0c7a6..85b7ccfb 100644 --- a/libsepol/include/sepol/policydb/ebitmap.h +++ b/libsepol/include/sepol/policydb/ebitmap.h @@ -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); diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index bd98c0f8..fb20e994 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -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) + 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)); + } + + 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; diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c index a21f18c0..1a49aa5f 100644 --- a/libsepol/tests/test-ebitmap.c +++ b/libsepol/tests/test-ebitmap.c @@ -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 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 2/7] libsepol: add ebitmap_init_range 2022-07-12 16:08 ` [PATCH 2/7] libsepol: add ebitmap_init_range Christian Göttsche @ 2022-07-18 20:43 ` James Carter 0 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:43 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > 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(). > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> > --- > libsepol/include/sepol/policydb/ebitmap.h | 1 + > libsepol/src/ebitmap.c | 49 +++++++++++++++++++++++ > libsepol/tests/test-ebitmap.c | 32 +++++++++++++++ > 3 files changed, 82 insertions(+) > > diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h > index 81d0c7a6..85b7ccfb 100644 > --- a/libsepol/include/sepol/policydb/ebitmap.h > +++ b/libsepol/include/sepol/policydb/ebitmap.h > @@ -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); > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index bd98c0f8..fb20e994 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -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) > + 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 > + 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; > diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c > index a21f18c0..1a49aa5f 100644 > --- a/libsepol/tests/test-ebitmap.c > +++ b/libsepol/tests/test-ebitmap.c > @@ -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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 3/7] libsepol/cil: use ebitmap_init_range 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche 2022-07-12 16:08 ` [PATCH 2/7] libsepol: add ebitmap_init_range Christian Göttsche @ 2022-07-12 16:08 ` Christian Göttsche 2022-07-18 20:44 ` James Carter 2022-07-12 16:08 ` [PATCH 4/7] libsepol: optimize ebitmap_not Christian Göttsche ` (4 subsequent siblings) 6 siblings, 1 reply; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux 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. Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- libsepol/cil/src/cil_post.c | 30 +++++++++--------------------- 1 file changed, 9 insertions(+), 21 deletions(-) diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c index 714ce227..6e95225f 100644 --- a/libsepol/cil/src/cil_post.c +++ b/libsepol/cil/src/cil_post.c @@ -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 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 3/7] libsepol/cil: use ebitmap_init_range 2022-07-12 16:08 ` [PATCH 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche @ 2022-07-18 20:44 ` James Carter 0 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:44 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > 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. > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> Acked-by: James Carter <jwcart2@gmail.com> > --- > libsepol/cil/src/cil_post.c | 30 +++++++++--------------------- > 1 file changed, 9 insertions(+), 21 deletions(-) > > diff --git a/libsepol/cil/src/cil_post.c b/libsepol/cil/src/cil_post.c > index 714ce227..6e95225f 100644 > --- a/libsepol/cil/src/cil_post.c > +++ b/libsepol/cil/src/cil_post.c > @@ -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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 4/7] libsepol: optimize ebitmap_not 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche 2022-07-12 16:08 ` [PATCH 2/7] libsepol: add ebitmap_init_range Christian Göttsche 2022-07-12 16:08 ` [PATCH 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche @ 2022-07-12 16:08 ` Christian Göttsche 2022-07-18 20:46 ` James Carter 2022-07-12 16:08 ` [PATCH 5/7] libsepol: optimize ebitmap_and Christian Göttsche ` (3 subsequent siblings) 6 siblings, 1 reply; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux Iterate on nodes instead of single bits to save node resolution for each single bit. Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 42 insertions(+), 6 deletions(-) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index fb20e994..6a63e559 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -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 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 4/7] libsepol: optimize ebitmap_not 2022-07-12 16:08 ` [PATCH 4/7] libsepol: optimize ebitmap_not Christian Göttsche @ 2022-07-18 20:46 ` James Carter 0 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:46 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > Iterate on nodes instead of single bits to save node resolution for each > single bit. > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> Acked-by: James Carter <jwcart2@gmail.com> > --- > libsepol/src/ebitmap.c | 48 ++++++++++++++++++++++++++++++++++++------ > 1 file changed, 42 insertions(+), 6 deletions(-) > > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index fb20e994..6a63e559 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 5/7] libsepol: optimize ebitmap_and 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche ` (2 preceding siblings ...) 2022-07-12 16:08 ` [PATCH 4/7] libsepol: optimize ebitmap_not Christian Göttsche @ 2022-07-12 16:08 ` Christian Göttsche 2022-07-18 20:47 ` James Carter 2022-07-12 16:08 ` [PATCH 6/7] libsepol: optimize ebitmap_xor Christian Göttsche ` (2 subsequent siblings) 6 siblings, 1 reply; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux Iterate on nodes instead of single bits to save node resolution for each single bit. Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- libsepol/src/ebitmap.c | 42 +++++++++++++++++++++++++++++++++++------- 1 file changed, 35 insertions(+), 7 deletions(-) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index 6a63e559..c3d706e9 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -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; } -- 2.36.1 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 5/7] libsepol: optimize ebitmap_and 2022-07-12 16:08 ` [PATCH 5/7] libsepol: optimize ebitmap_and Christian Göttsche @ 2022-07-18 20:47 ` James Carter 0 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:47 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > Iterate on nodes instead of single bits to save node resolution for each > single bit. > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> > --- > libsepol/src/ebitmap.c | 42 +++++++++++++++++++++++++++++++++++------- > 1 file changed, 35 insertions(+), 7 deletions(-) > > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index 6a63e559..c3d706e9 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -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; I would like to see braces around the last two clauses. Thanks, Jim > } > + > + if (prev) > + dst->highbit = prev->startbit + MAPSIZE; > + > return 0; > } > > -- > 2.36.1 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 6/7] libsepol: optimize ebitmap_xor 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche ` (3 preceding siblings ...) 2022-07-12 16:08 ` [PATCH 5/7] libsepol: optimize ebitmap_and Christian Göttsche @ 2022-07-12 16:08 ` Christian Göttsche 2022-07-18 20:48 ` James Carter 2022-07-12 16:08 ` [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche 2022-07-18 20:39 ` [PATCH 1/7] libsepol/tests: add ebitmap tests James Carter 6 siblings, 1 reply; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux Iterate on nodes instead of single bits to save node resolution for each single bit. Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 43 insertions(+), 6 deletions(-) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index c3d706e9..e0541abb 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -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 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 6/7] libsepol: optimize ebitmap_xor 2022-07-12 16:08 ` [PATCH 6/7] libsepol: optimize ebitmap_xor Christian Göttsche @ 2022-07-18 20:48 ` James Carter 0 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:48 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > Iterate on nodes instead of single bits to save node resolution for each > single bit. > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> Acked-by: James Carter <jwcart2@gmail.com> > --- > libsepol/src/ebitmap.c | 49 ++++++++++++++++++++++++++++++++++++------ > 1 file changed, 43 insertions(+), 6 deletions(-) > > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index c3d706e9..e0541abb 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche ` (4 preceding siblings ...) 2022-07-12 16:08 ` [PATCH 6/7] libsepol: optimize ebitmap_xor Christian Göttsche @ 2022-07-12 16:08 ` Christian Göttsche 2022-07-18 20:48 ` James Carter 2022-07-18 20:39 ` [PATCH 1/7] libsepol/tests: add ebitmap tests James Carter 6 siblings, 1 reply; 14+ messages in thread From: Christian Göttsche @ 2022-07-12 16:08 UTC (permalink / raw) To: selinux 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(). Signed-off-by: Christian Göttsche <cgzones@googlemail.com> --- libsepol/src/ebitmap.c | 3 --- 1 file changed, 3 deletions(-) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index e0541abb..d0f7daba 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -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 ^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations 2022-07-12 16:08 ` [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche @ 2022-07-18 20:48 ` James Carter 0 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:48 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > 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(). > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> Acked-by: James Carter <jwcart2@gmail.com> > --- > libsepol/src/ebitmap.c | 3 --- > 1 file changed, 3 deletions(-) > > diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c > index e0541abb..d0f7daba 100644 > --- a/libsepol/src/ebitmap.c > +++ b/libsepol/src/ebitmap.c > @@ -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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH 1/7] libsepol/tests: add ebitmap tests 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche ` (5 preceding siblings ...) 2022-07-12 16:08 ` [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche @ 2022-07-18 20:39 ` James Carter 6 siblings, 0 replies; 14+ messages in thread From: James Carter @ 2022-07-18 20:39 UTC (permalink / raw) To: Christian Göttsche; +Cc: SElinux list On Tue, Jul 12, 2022 at 12:09 PM Christian Göttsche <cgzones@googlemail.com> wrote: > > Preparation for several ebitmap related optimizations. > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com> > --- > 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 > > diff --git a/libsepol/tests/libsepol-tests.c b/libsepol/tests/libsepol-tests.c > index dc8fd5ce..5ae6bedc 100644 > --- a/libsepol/tests/libsepol-tests.c > +++ b/libsepol/tests/libsepol-tests.c > @@ -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); > diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c > new file mode 100644 > index 00000000..a21f18c0 > --- /dev/null > +++ b/libsepol/tests/test-ebitmap.c > @@ -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; > +} > + > +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. > + 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. > + 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); > + > + 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. > + 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)); > + 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. > + { > + 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); > + 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. > + { > + 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); > + 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 > + { > + 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; > +} > diff --git a/libsepol/tests/test-ebitmap.h b/libsepol/tests/test-ebitmap.h > new file mode 100644 > index 00000000..952a0421 > --- /dev/null > +++ b/libsepol/tests/test-ebitmap.h > @@ -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 > ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2022-07-18 20:48 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-07-12 16:08 [PATCH 1/7] libsepol/tests: add ebitmap tests Christian Göttsche 2022-07-12 16:08 ` [PATCH 2/7] libsepol: add ebitmap_init_range Christian Göttsche 2022-07-18 20:43 ` James Carter 2022-07-12 16:08 ` [PATCH 3/7] libsepol/cil: use ebitmap_init_range Christian Göttsche 2022-07-18 20:44 ` James Carter 2022-07-12 16:08 ` [PATCH 4/7] libsepol: optimize ebitmap_not Christian Göttsche 2022-07-18 20:46 ` James Carter 2022-07-12 16:08 ` [PATCH 5/7] libsepol: optimize ebitmap_and Christian Göttsche 2022-07-18 20:47 ` James Carter 2022-07-12 16:08 ` [PATCH 6/7] libsepol: optimize ebitmap_xor Christian Göttsche 2022-07-18 20:48 ` James Carter 2022-07-12 16:08 ` [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations Christian Göttsche 2022-07-18 20:48 ` James Carter 2022-07-18 20:39 ` [PATCH 1/7] libsepol/tests: add ebitmap tests James Carter
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).