From patchwork Tue Jul 19 15:30:38 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922689 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 25890C43334 for ; Tue, 19 Jul 2022 15:31:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237618AbiGSPbF (ORCPT ); Tue, 19 Jul 2022 11:31:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33910 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230253AbiGSPbD (ORCPT ); Tue, 19 Jul 2022 11:31:03 -0400 Received: from mail-ed1-x52f.google.com (mail-ed1-x52f.google.com [IPv6:2a00:1450:4864:20::52f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9C4CD5885F for ; Tue, 19 Jul 2022 08:31:00 -0700 (PDT) Received: by mail-ed1-x52f.google.com with SMTP id x91so20137434ede.1 for ; Tue, 19 Jul 2022 08:31:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=XpdIq7KJay1vnNNeqJAQUK4VClf+H7aQKoY5lfY+WZU=; b=oVMnEV6dxY5/pwQqUEdzbu9L8THe073HvDBoHIhawRVIyJNlL0WXe8IekiIfhcHfCb WocD0/NhyKHoKFFz/B/D4+dh+6wrx3zDmxWYT8cTRV5H4M3qxKj3vTB8JhhXQbyMq5yT RxMvNIo6YFWJkORk4En54nxmkbGoW3tHt6Hd3Uyy2pFBf1OiFy/39kEprMxJi2o4Ye1x niETAZgXO4e0DVEvDkmSs5ZUVKuhIFOrnfwo847K7T+Ct/+c/Wh70KMG1sq795s160lk khcaE9UZEsnpOXeaclRLYNNgifbYlRYgEceTalWdF8OTet8eGQUheEnZEksOUqB4d3Yp Oxrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=XpdIq7KJay1vnNNeqJAQUK4VClf+H7aQKoY5lfY+WZU=; b=yaa3HKtZ0Weth80ZyT6zrFBZseSnYeKYA/GNYGtps/gkADHNjuF2NyratlqkMcVtQb GRtivg0iOJF88ARbPdvUonbMSVd8BnB8+WTYAb4FO+urPIO6CGARUZCglX9dTRF52Dw5 e/IpTt/Y2TKx1ANVcm4+8+HK5TfgG4pIqxq2JtYU7nrua3Z83vEadbXZ14G5LtieM2b3 tSAyaB7MiX+d/2px8nmXwoLEpopRECVpJo7KcXvm8Tw/t67MyedhFRNXfWpN5/vTdd2Q 7r08w/QpwZPInM4+qIUfYvSuyXbrWXBeHHKaL3YnV83SukLI4j7kTEE+wHm6VPQvEZnz L68A== X-Gm-Message-State: AJIora9Uk2x7NcSHbrtpgvnjCLqqmFkSa92N47BRbccFAC0kwK7BzCQT bOGWY+C8IJ2t7zJzO8qVQxYS2n4YU/SX/Q== X-Google-Smtp-Source: AGRyM1vG2ZoenCEh5YxOmyzga93Td9ej7h1+xDV11HBanlogPLcmRXqFQasxrXgkVOLZBX+3rYzbUA== X-Received: by 2002:a05:6402:3707:b0:437:61f9:57a9 with SMTP id ek7-20020a056402370700b0043761f957a9mr34495397edb.1.1658244658997; Tue, 19 Jul 2022 08:30:58 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.30.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:30:58 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 1/7] libsepol/tests: add ebitmap tests Date: Tue, 19 Jul 2022 17:30:38 +0200 Message-Id: <20220719153045.70041-1-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Preparation for several ebitmap related optimizations. Signed-off-by: Christian Göttsche Acked-by: James Carter --- v2: - add more tests for multi node ebitmaps and for bits set at node bounds - test ebitmap_for_each_bit() --- libsepol/tests/libsepol-tests.c | 2 + libsepol/tests/test-ebitmap.c | 1048 +++++++++++++++++++++++++++++++ libsepol/tests/test-ebitmap.h | 10 + 3 files changed, 1060 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..fad5bd75 --- /dev/null +++ b/libsepol/tests/test-ebitmap.c @@ -0,0 +1,1048 @@ +#include "test-ebitmap.h" + +#include +#include + +#include +#include + +#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; + + /* verify idempotence */ + ebitmap_init(&e); + ebitmap_init(&e); + ebitmap_init(&e); + + CU_ASSERT(ebitmap_is_empty(&e)); + CU_ASSERT_PTR_NULL(ebitmap_startnode(&e)); + + /* verify idempotence */ + 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)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 63, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 63, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 64, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 64, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1022, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1022, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1023, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1023, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1024, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1024, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1025, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1025, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 255, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 255, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 256, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 256, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 639, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 639, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 640, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 640, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 900, 1), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 900, 1), 0); + CU_ASSERT(ebitmap_cmp(&e1, &e2)); + + ebitmap_destroy(&e2); + + CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2)); + + ebitmap_destroy(&e1); + + CU_ASSERT(ebitmap_cmp(&e1, &e2)); +} + +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(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, 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); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 1), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1023), 1); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 1), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1024); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 1); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 1), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 6); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 1); + + { + ebitmap_node_t *n; + unsigned int bit, count; + + /* iterate all allocated bits */ + count = 0; + ebitmap_for_each_bit(&e, n, bit) { + CU_ASSERT( bit < 64 || + (64 <= bit && bit < 128) || + (960 <= bit && bit < 1024) || + (1024 <= bit && bit < 1088)); + count++; + } + CU_ASSERT_EQUAL(count, 4 * 64); + + count = 0; + ebitmap_for_each_positive_bit(&e, n, bit) { + CU_ASSERT(bit == 10 || + bit == 50 || + bit == 100 || + bit == 1023 || + bit == 1024 || + bit == 1050); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, bit), 1); + count++; + } + CU_ASSERT_EQUAL(count, 6); + } + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1024, 0), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 5); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1050); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1024), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1050, 0), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 4); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 1050), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 0), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023); + 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), 2); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 0), 0); + CU_ASSERT_FALSE(ebitmap_is_empty(&e)); + CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1); + CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 1023); + CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 1023, 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, 1023), 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, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 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, 430, 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, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 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, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 383, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 384, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 449, 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, 319, 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(&e12, 319, 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, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 383, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 384, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 449, 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); + } + + { + ebitmap_t e5; + ebitmap_t e6; + ebitmap_t e56; + ebitmap_t dst; + + ebitmap_init(&e5); + ebitmap_init(&e6); + ebitmap_init(&e56); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 319, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_and(&dst, &e5, &e6), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e56)); + + ebitmap_destroy(&dst); + ebitmap_destroy(&e56); + ebitmap_destroy(&e6); + ebitmap_destroy(&e5); + } +} + +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); + } + + { + ebitmap_t e5; + ebitmap_t e6; + ebitmap_t e56; + ebitmap_t dst; + + ebitmap_init(&e5); + ebitmap_init(&e6); + ebitmap_init(&e56); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 64, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 320, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e5, &e6), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e56)); + + ebitmap_destroy(&dst); + ebitmap_destroy(&e56); + ebitmap_destroy(&e6); + ebitmap_destroy(&e5); + } +} + +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); + } + + { + ebitmap_t e5; + ebitmap_t e5not; + ebitmap_node_t *n; + unsigned int bit; + + ebitmap_init(&e5); + ebitmap_init(&e5not); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0); + + for (bit = 0; bit < 317; bit++) + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 1), 0); + ebitmap_for_each_positive_bit(&e5, n, bit) + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, bit, 0), 0); + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 317), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e5not)); + + ebitmap_destroy(&dst); + } + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 318), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e5not)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5not, 317, 1), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e5not)); + + ebitmap_destroy(&dst); + } + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_not(&dst, &e5, 319), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e5not)); + + ebitmap_destroy(&dst); + } + + ebitmap_destroy(&e5not); + ebitmap_destroy(&e5); + } +} + +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); + } + + { + ebitmap_t e5; + ebitmap_t e6; + ebitmap_t e56; + + ebitmap_init(&e5); + ebitmap_init(&e6); + ebitmap_init(&e56); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 63, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 191, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 318, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e5, 319, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 64, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 192, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 319, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e6, 320, 1), 0); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 63, 1), 0); + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 191, 1), 0); + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 317), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e56)); + + ebitmap_destroy(&dst); + } + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 318), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e56)); + + ebitmap_destroy(&dst); + } + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 319), 0); + CU_ASSERT_FALSE(ebitmap_cmp(&dst, &e56)); + + CU_ASSERT_EQUAL(ebitmap_set_bit(&e56, 318, 1), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e56)); + + ebitmap_destroy(&dst); + } + + { + ebitmap_t dst; + + CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e5, &e6, 320), 0); + CU_ASSERT(ebitmap_cmp(&dst, &e56)); + + ebitmap_destroy(&dst); + } + + ebitmap_destroy(&e56); + ebitmap_destroy(&e6); + ebitmap_destroy(&e5); + } +} + +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 + +int ebitmap_test_init(void); +int ebitmap_test_cleanup(void); +int ebitmap_add_tests(CU_pSuite suite); + +#endif /* TEST_EBITMAP_H__ */ From patchwork Tue Jul 19 15:30:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922690 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1A565C43334 for ; Tue, 19 Jul 2022 15:31:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233392AbiGSPbI (ORCPT ); Tue, 19 Jul 2022 11:31:08 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34042 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237756AbiGSPbH (ORCPT ); Tue, 19 Jul 2022 11:31:07 -0400 Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 33B345885F for ; Tue, 19 Jul 2022 08:31:05 -0700 (PDT) Received: by mail-ej1-x634.google.com with SMTP id z23so27876894eju.8 for ; Tue, 19 Jul 2022 08:31:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=OTvYFVbriaW0Niv5/huzg4LHWamuGhBYbTQRk7sWhSM=; b=g6lwDuCdD4Uiae7hxBdhAyrH3J7ZTqoiNKKSVs7qIqE9UPViWYJ+7GWhrLUv7L2Yi4 tUsxvlhafc64D4OmmDIArS1QR22OpekDBfYbPLpugObbq1cbFrOFpYFiTT69+nz+1cdz 4CM6guDop8Q/iyGWAyZlD2OpqWX+EFaB/G/D3rptHdPdc29j77KjsOV2BvwuSnrTBGmU ijSb87u4xKggNUpWpw+8F1anwb1ndV1nb3bMbp4jr7kCOfryjpNfjE+Jx9C6CayyjGhn xjwkeCE0A7OVy+hwGG3ssYCEvoy04gdV252JbUsMMgBPHJ+gq1ne2GuE0Zfpl8IOfK35 tAeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=OTvYFVbriaW0Niv5/huzg4LHWamuGhBYbTQRk7sWhSM=; b=FtjvGCvyr43C4Q6bheL2aACnxIjuwEXbxwgabzsQQUH+8ccmzKxKNeyWRcf0gp49U4 1rnH6rBOQDdTF1+waKL6owkeUy06pgMxElsM1HaXANnOPnimIgBal+gTng5Yl/OoBck3 K0/5w2p5V1Ovk2Bqqtle2/h9NDvnVTQa01cSL8VO74Q4aMqhCjKzwSw0WNmqr+nmR7Ac zu+MO0rxKtfHSduinG6nTQbjmLDXG3ky9YIgpi1LlF1JnUWrfK4KTmhdq9amllA+L+fx Gthn43ftiKlkubjMvqJQf8sbgWTMOIlXCMeYCXIhs4HDf427UweH55ZRgJIKfftQv+A3 IB8A== X-Gm-Message-State: AJIora903oCSulcvn1ZD5Lh967UBiGlI/sQV0w0BxOwmh+Hl9N5dzePG 1iGwSXO8Teg0Ki4t+xlkfEXKINIz5Jst7w== X-Google-Smtp-Source: AGRyM1vsRHJZCC442wTcuV+2vhB1WnQFsbteBee0M6A5vioeJ9u/QiZq1DPspEGCNn2qh9h0QnGy4A== X-Received: by 2002:a17:907:2bc6:b0:72e:ceea:862b with SMTP id gv6-20020a1709072bc600b0072eceea862bmr28618919ejc.134.1658244663262; Tue, 19 Jul 2022 08:31:03 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.31.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:31:02 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 2/7] libsepol: add ebitmap_init_range Date: Tue, 19 Jul 2022 17:30:39 +0200 Message-Id: <20220719153045.70041-2-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220719153045.70041-1-cgzones@googlemail.com> References: <20220719153045.70041-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org 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 --- v2: use braces for all if-else branches when used for at least one of them --- 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..0f9afd62 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 fad5bd75..8774555e 100644 --- a/libsepol/tests/test-ebitmap.c +++ b/libsepol/tests/test-ebitmap.c @@ -253,6 +253,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; @@ -1038,6 +1069,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); From patchwork Tue Jul 19 15:30:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922691 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C2DECCCA483 for ; Tue, 19 Jul 2022 15:31:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S236090AbiGSPbJ (ORCPT ); Tue, 19 Jul 2022 11:31:09 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34048 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S237731AbiGSPbH (ORCPT ); Tue, 19 Jul 2022 11:31:07 -0400 Received: from mail-ej1-x62b.google.com (mail-ej1-x62b.google.com [IPv6:2a00:1450:4864:20::62b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8C0F558870 for ; Tue, 19 Jul 2022 08:31:05 -0700 (PDT) Received: by mail-ej1-x62b.google.com with SMTP id os14so27907796ejb.4 for ; Tue, 19 Jul 2022 08:31:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=zWHpdd1Gp2i82c79opTYMnv9mwhyMyNRPmGXCJAnIZ0=; b=KanbOXVuJ6HVRNl0V0lNuxLyzhVlWIAFHaZOr1oCWnHea7xdRPaJiSGlANTGAFmeQs 1MIcLdXINl7sVsmBtiymquVvhuwfs5o2mZYYUZUO17wi96w9VnKJ4kANNhdY/jvZ3Tpr brjBiCSIS5vfvSMf9JED6Ha5gg80HqWDuF/GhTQSAYvFoP5iQmocQM/oHYhvxCGuUBhk 6nEuec2xRRdE8CkgtiwhoyAaibiAE5dw7yJyoK2SG/5fpwM/RD8iUQJ1gdDgywHk0bSf 9LBjDrAOqxT5k/mwlUpzMFoVXkBSiEygRnJu+IuMxbkAqJ7NeMUV/FaRC8oxVSyCyqZ8 RNcA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=zWHpdd1Gp2i82c79opTYMnv9mwhyMyNRPmGXCJAnIZ0=; b=1RHOuiheSOuHBPHo67QeiRK+vAUTwT7QULHR25nnmnzHEnCaTgB0pLR/gnEUan6Wct gz9pA4SFvYqxE20WBKlFnlW3HxTbBonQ/zxCqdD1d515k0pTC6o7fv6EaiEiVdzUsqns twxtwef4L75JGFUUnbgth1Cbqu6pWQECyBMq3dad1+lSUsIqxGqMibdQH2S3vn25lguo htQW0020wzkrjncv7G8my9P4QYUaBkqpHyS6QSOqpGeFPcUjm6+LB5imNUwGURQAIT8n qzqwGmdFLJnITwSq7MHOB4KECK0clDrCDyPOQyTCYUbpOLTDlPv9ugh/pMwXe2H1attd /Qyg== X-Gm-Message-State: AJIora/hHkhC2XmSuFnLh1vnsGJtV+KohcP2DbofUa/YwzCtw/xj4F05 B6pL9Up4JPSRNk1c3kXz4PzNarnaWsWBsA== X-Google-Smtp-Source: AGRyM1sc8htJnjrttKZuDPGFgAPL1AE51LrqNwzKuUnBs8JW7+XBft8lsPJFQwgKPt/MaVi/GaFqig== X-Received: by 2002:a17:907:2cc8:b0:72b:52b3:68e with SMTP id hg8-20020a1709072cc800b0072b52b3068emr31782333ejc.298.1658244663990; Tue, 19 Jul 2022 08:31:03 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.31.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:31:03 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 3/7] libsepol/cil: use ebitmap_init_range Date: Tue, 19 Jul 2022 17:30:40 +0200 Message-Id: <20220719153045.70041-3-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220719153045.70041-1-cgzones@googlemail.com> References: <20220719153045.70041-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org 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 --- 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 { From patchwork Tue Jul 19 15:30:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922692 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 10FFFC433EF for ; Tue, 19 Jul 2022 15:31:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237006AbiGSPbK (ORCPT ); Tue, 19 Jul 2022 11:31:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34050 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230253AbiGSPbH (ORCPT ); Tue, 19 Jul 2022 11:31:07 -0400 Received: from mail-ej1-x630.google.com (mail-ej1-x630.google.com [IPv6:2a00:1450:4864:20::630]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4046658868 for ; Tue, 19 Jul 2022 08:31:06 -0700 (PDT) Received: by mail-ej1-x630.google.com with SMTP id b11so27837777eju.10 for ; Tue, 19 Jul 2022 08:31:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=9Oi1SP+HLX1gKBYbPAvOxTHVFnYtctn7wi4GBcEPx2A=; b=oJ42SaqOM19KAziV4LKgd3p8TJeO5gmU3OKGQ6wK+9+xx8qtJhexJcjjF5MF20PG3T MK4q2OaXSOvYpi+EyugPLJXPk+OVp6hX7BVctXvOf768RErF2ENgXvn1MDyThzmw3ICu E+OFT6tSDZx2lUO5Xsgp+512E2kRVZuoMFqPi1LPlYazj+DSqXsE9Ib5DonlPy0Qi8fx pg9jmYaRwgfdehJJetac3OgUNeokhkLjJcYHiCvaW1eYWd0OjK4z2CqZax0sXARKsD6g ExFikzSpXhcG2bx8hhfVJ++PEkLToo63sfTu+pZqoydcOC6XDQNYMbSIugFk/2m43ZB0 pkwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=9Oi1SP+HLX1gKBYbPAvOxTHVFnYtctn7wi4GBcEPx2A=; b=fmPGKzr4jlAZ4BlrXLuPkvRfFPaauA9p103EYJzNTPNur4w9bId5Bb6RhRtIyLqPod rTnlxX9pFbFjJYHgThWW6Ikf3xQoFHmHeed44sfoqOec3JadCEvkm4t416YwoidVU0v0 71QgB+95OwK6spTe9zPx+/K4ZVXO3Ol+JACQ+0IlbFPlloZ4XvRU1Seq5mqgQtq7Apfl 1eOqSK9ojxEBxxf9DdqWwSrEz0fABUHyM/RcoOY8PtHg3Sb6YvhBmNKWoJPM3AHnPBL9 sVTPjybnKwG3+lyhSvKi2tFqgB9kRgs5lof6QId8cfX9Dy5f9qJapV4Jc3J8ecrFnUAV SEKg== X-Gm-Message-State: AJIora+KHqjVdVoszr7Gegru3MH16uNclJffTkzFRB2BXhy48NZSBnZI uoRUvLtBGRe4ZvxW2OLMdqSCFebFQoA6pw== X-Google-Smtp-Source: AGRyM1uX13vyp7BQUkYahrPnGPs4L8vj9apruheSug9tew/0z+6O8GwlYipBjXd2XUvQUsUBvZHAYg== X-Received: by 2002:a17:907:a40b:b0:72b:64e3:4c5e with SMTP id sg11-20020a170907a40b00b0072b64e34c5emr32026633ejc.612.1658244664803; Tue, 19 Jul 2022 08:31:04 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.31.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:31:04 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 4/7] libsepol: optimize ebitmap_not Date: Tue, 19 Jul 2022 17:30:41 +0200 Message-Id: <20220719153045.70041-4-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220719153045.70041-1-cgzones@googlemail.com> References: <20220719153045.70041-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Iterate on nodes instead of single bits to save node resolution for each single bit. Signed-off-by: Christian Göttsche --- 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 0f9afd62..c9164c5e 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; } From patchwork Tue Jul 19 15:30:42 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922694 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id EB493CCA483 for ; Tue, 19 Jul 2022 15:31:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S237731AbiGSPbM (ORCPT ); Tue, 19 Jul 2022 11:31:12 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34096 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234127AbiGSPbI (ORCPT ); Tue, 19 Jul 2022 11:31:08 -0400 Received: from mail-ed1-x533.google.com (mail-ed1-x533.google.com [IPv6:2a00:1450:4864:20::533]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2E9265886C for ; Tue, 19 Jul 2022 08:31:07 -0700 (PDT) Received: by mail-ed1-x533.google.com with SMTP id y4so20108799edc.4 for ; Tue, 19 Jul 2022 08:31:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=NYQLsg+OM3i1gj8SShF2mSYB6+VprKWtjfjk169htWo=; b=bSIs0LSmy0oPy4cCodR8hhgX/VmTIcbN6uvsMCvhUqrA7QqVaTd4c+WKG5YbJDj6MZ XmcTBYXEpQ70a+LRd08lU+zpdCj0JPbsqHOxVBwNiyivv/WTKdO5a45+MYg4ULVLuBJ1 Pr2INsM7RtGgeHM/GbbQeJthUjGdXmZhQcCuzWgRdKxD9BkkClWoGTO8jkwcKrTtEydW WLF2LkGlCm++XkHBI81q4qmxIOg48LMIapEWT4WU3+iW+5HEthJEPXarax8WBxcmwZ1F 2ISdOh0nvSHufHkdOGuFELdMWQsinjEKTU5qkdOfaaAnmhqSWxLUOML4A+zIjKv2huMV V+/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=NYQLsg+OM3i1gj8SShF2mSYB6+VprKWtjfjk169htWo=; b=IwtuUxd/L3AnahvrO8/Ek86MXdcOxMqG3PU6h/f7yF86OuIFDJRA+VKGPZlXU/JkKK tQTPWxl7mWrN59GguSqGV6/D5DA2FrEmcFbuN6x7YxtQwBm7SFighGVsUJ9e5MUtGrTY yabQv3iYqRgB82SXecoobtCL4+68VHefZ3eEfDdHrqlcvDMXUuiomUmRVODutee+m0vj CwXh0OGBsflNM/tdTC7BKPsCRWG7GttFlh8Hu8nKVakDiD1/GXYLSxaVw3ID1ebHcb7f N09zRxcL+95Ri/5NEIZ+5bkEOmdzBDQ0lXR/MGRAmLDfdOq7kBEVPttKumw1veN3ncFX GLVQ== X-Gm-Message-State: AJIora+WMOVkGIJbcYs+In9/InJJVdF40XVSNHfJpb8jHIay6Golbg21 bAFMcEelsE0A4xmqWitBF2c3WfAY6G+mCg== X-Google-Smtp-Source: AGRyM1tn3IWEpWqi9Z12gq3TA2qldfk7zOtB8DzbK6oTafcNjBOime0h1usoYfKjZn7gvDasccsHbA== X-Received: by 2002:a05:6402:3553:b0:43a:dba8:9f65 with SMTP id f19-20020a056402355300b0043adba89f65mr44041247edd.323.1658244665518; Tue, 19 Jul 2022 08:31:05 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.31.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:31:05 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 5/7] libsepol: optimize ebitmap_and Date: Tue, 19 Jul 2022 17:30:42 +0200 Message-Id: <20220719153045.70041-5-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220719153045.70041-1-cgzones@googlemail.com> References: <20220719153045.70041-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Iterate on nodes instead of single bits to save node resolution for each single bit. Signed-off-by: Christian Göttsche --- v2: use braces for all if-else branches when used for at least one of them --- libsepol/src/ebitmap.c | 41 +++++++++++++++++++++++++++++++++++------ 1 file changed, 35 insertions(+), 6 deletions(-) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index c9164c5e..6dbbddfd 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -74,15 +74,44 @@ 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; } From patchwork Tue Jul 19 15:30:43 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922693 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 73AC7C43334 for ; Tue, 19 Jul 2022 15:31:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230163AbiGSPbL (ORCPT ); Tue, 19 Jul 2022 11:31:11 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34098 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233950AbiGSPbI (ORCPT ); Tue, 19 Jul 2022 11:31:08 -0400 Received: from mail-ed1-x52e.google.com (mail-ed1-x52e.google.com [IPv6:2a00:1450:4864:20::52e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E1AAE237E1 for ; Tue, 19 Jul 2022 08:31:07 -0700 (PDT) Received: by mail-ed1-x52e.google.com with SMTP id y8so20128209eda.3 for ; Tue, 19 Jul 2022 08:31:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=xCtNwp6k/KqLKgW3B8b22oqNaVxmuyDq1r807l0Ud9I=; b=fq9hvniqeGey9Npr3ae6ymO1dzfWDQCTvngVQq16MhChocC51GGvDD0aLL5cCKwwI2 R/GBg3UcRgzpMzUM79tWtzykMXoKAFgm9tJGiXpYJzqcF89KdkAAqZRxhsJu7/YGSURP /4lzLgAOg01fdgkyZ8VyK87mKHqdHoxco2iHtFQELMWIRNuDh3zJmY6VqZ/Xa8jLjAqf b7KAJlkbWhd0C2e1eyEUCO3w2WC1WiLa/zZWFA9UpX+w6xlG3NqEVrJRppQfrbM+LCZd 6ToIqIyTNIB0RPC975o6t95RZ8lTII2KH/dgnKswpS1q6o38AkYdJeZvCPUvOB+tkxWb CZDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=xCtNwp6k/KqLKgW3B8b22oqNaVxmuyDq1r807l0Ud9I=; b=1Vuh4CPxqzODdvFw5DWFEcmK2Oz5x2q6b7PbFnvLnto1/oLjDWNB057LZp7vBjJvYn Gp4TdQCjI+5SPdjG1y+qbVrTxN4w6SzAYrxMvE6O1lAZ93BkhuNW/Qyo39Ea/0lkXlJq l/p07SRf3q/nz9aWx5sEuHdxNkk2gA73uD8UkkcjXa9xhtYSJKyN2OebH14t7ghReDXz qruI/eQKwM3GjiI9CJKQW7PLkaOIDlzuRGidMPfyXvgL7UgmfO1xjNGmQ7q5AtVgtlKt M3RUbImswzsJb76657t/GceFrVqwBrv7jrdgnmiyqdkaXtRzx3g5HuVUlbe9iwHncthr Di3w== X-Gm-Message-State: AJIora8wl+JuaIyVOy9UyeojI1oPyFAr8BrKxTRuyjFYh7V/Mxq+HyL0 ScTj3/n3j8H4T0Fam1+14gWUjRZtlMHzHw== X-Google-Smtp-Source: AGRyM1s5I/JD2o+wZLxRSje/vvNjMWxzBfZhaJS4rU6axnyX+eVL8B61/6nrD77e9BMDQGiQhtrUOA== X-Received: by 2002:a05:6402:440f:b0:435:2e63:aca9 with SMTP id y15-20020a056402440f00b004352e63aca9mr43623890eda.162.1658244666344; Tue, 19 Jul 2022 08:31:06 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.31.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:31:06 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 6/7] libsepol: optimize ebitmap_xor Date: Tue, 19 Jul 2022 17:30:43 +0200 Message-Id: <20220719153045.70041-6-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220719153045.70041-1-cgzones@googlemail.com> References: <20220719153045.70041-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Iterate on nodes instead of single bits to save node resolution for each single bit. Signed-off-by: Christian Göttsche --- 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 6dbbddfd..7d26f949 100644 --- a/libsepol/src/ebitmap.c +++ b/libsepol/src/ebitmap.c @@ -117,14 +117,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; } From patchwork Tue Jul 19 15:30:44 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Christian_G=C3=B6ttsche?= X-Patchwork-Id: 12922695 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7463FCCA485 for ; Tue, 19 Jul 2022 15:31:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230253AbiGSPbM (ORCPT ); Tue, 19 Jul 2022 11:31:12 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34112 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S236458AbiGSPbJ (ORCPT ); Tue, 19 Jul 2022 11:31:09 -0400 Received: from mail-ej1-x633.google.com (mail-ej1-x633.google.com [IPv6:2a00:1450:4864:20::633]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8E5845885F for ; Tue, 19 Jul 2022 08:31:08 -0700 (PDT) Received: by mail-ej1-x633.google.com with SMTP id l23so27886427ejr.5 for ; Tue, 19 Jul 2022 08:31:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=YYAya2IjPo0e6G7r+k7JrvFxc/U5lYIslrGMlcbbDvg=; b=Y/LMHPF6a81NuPuuAisd7c6z6pDiDwaNOTLKGxyj6KS7E1yLfbaSRVa4QVZfDXPbq8 uGscSZMhhmqeiGhL/aOcGKj7Wc1O0wgGYuhixvdQEaGuWYZQ4bngAvZ5l8grwod71EQR CH4uYvdLL1nyOShsSi5as2NXT8svBTK7gUdmfmRBYtM6YX2Z5HT3wcmDIsP1M6BL9x6O wMPREBY//66ohZtS4cKSWFpekzlnf6h2mbzAyECj1Tg20vY+/K97sZlWD8GrBSJfLsKM wcEjUWMJK4eNAYGepUr2ojhPveM3gr6bbNbIz/0ispLlsI2n7PEFTVfZPqC82mnfYt9j hc3A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=YYAya2IjPo0e6G7r+k7JrvFxc/U5lYIslrGMlcbbDvg=; b=HHctwG6qsbwe9bsu5lmGB3xiBlbsDSSyJlnBOqjlDiVdOyvDFJdM5dmSktA+iKM6Tc CRLjJhJqk2xuzQIo6c9AfGkQK/ctSHQg2rZxJXTQ1g4aPnQXiU8904dheguVVopmi7aB Ls5LLas9HZc+Sxq6lrKCdW6Roo5rxRF3aGtN4k1dEMmNYsBd1zPodN1kfNHBH2brGoTW hu5Kww30SOPCX8NOnJEiTxBJtsYuSyaZbgtAIo86sPCaJSb+5mM4RkUQUomd7EWAPaCT PSVBsy+MEfxn5K2IdTgjpqbrbQSP7MXMHE6PYKPEEJeByDKTdhzDIWYuHTpwXTg3xYqj lm0A== X-Gm-Message-State: AJIora/1vGrzxWkI9grncNG+o0KSsILTQBLdQniAHmQViaZ9QGgFkGD+ GNymJhG13ClGZZ21f4u17ajYGoZzOMF5rw== X-Google-Smtp-Source: AGRyM1vV3EBnGj9/I5wf7jg6y7FY7zfUQwd2z13PRr3wa/m7ND7LzTB+y6U6qMXVCbxTc4Joao6UPw== X-Received: by 2002:a17:907:728d:b0:72f:38d0:b8ae with SMTP id dt13-20020a170907728d00b0072f38d0b8aemr9218202ejc.30.1658244667107; Tue, 19 Jul 2022 08:31:07 -0700 (PDT) Received: from dlaptop.localdomain (dynamic-077-001-147-221.77.1.pool.telefonica.de. [77.1.147.221]) by smtp.gmail.com with ESMTPSA id 27-20020a170906311b00b0072b7b317aadsm6809621ejx.150.2022.07.19.08.31.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 19 Jul 2022 08:31:06 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: =?utf-8?q?Christian_G=C3=B6ttsche?= Subject: [PATCH v2 7/7] libsepol: skip superfluous memset calls in ebitmap operations Date: Tue, 19 Jul 2022 17:30:44 +0200 Message-Id: <20220719153045.70041-7-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220719153045.70041-1-cgzones@googlemail.com> References: <20220719153045.70041-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org 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 --- libsepol/src/ebitmap.c | 3 --- 1 file changed, 3 deletions(-) diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c index 7d26f949..3ec1042f 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; @@ -290,7 +289,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; @@ -430,7 +428,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));