From patchwork Tue Jul 12 16:08:52 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: 12915283 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 3A9E4CCA47F for ; Tue, 12 Jul 2022 16:09:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234228AbiGLQJQ (ORCPT ); Tue, 12 Jul 2022 12:09:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52520 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234245AbiGLQJJ (ORCPT ); Tue, 12 Jul 2022 12:09: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 4C83613DE9 for ; Tue, 12 Jul 2022 09:09:05 -0700 (PDT) Received: by mail-ej1-x633.google.com with SMTP id dn9so15149498ejc.7 for ; Tue, 12 Jul 2022 09:09:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=Th9symoIAedk8n4yZ9NYso7peFhQUZDzMX3JzdaOdRI=; b=B3xjxDDQTwmpV3BLQ/ADMMGPiqE7buqDD1gjEkLrAMMroPrCkglm2jq/SbVOA+Gt24 lZFOwq2DRDc0QUhXWdHuJ+F4wz6SJJ4qnVOrm8fRsQjtBbul0j0BNWq0Hvu+VUh+vKDK Rf8ls+Vu15G3SRXihgwRLqPnJ0daWWWrVEY/tlAysiWziLxaL9BH688PkSQqcfSEh+iD 8eOa2H/BTUTzq9gCKYBdr3T1U8V718Qiy1zIfnEojiHh8wbAF2W5tb8RWoBJJ49jvuxn BgUQbGxvPu9Ty3Yqiv8V6BJtyv8Lt9mqEdMjIPPMvBdc8kw+3EE9svOaO8uKwimJt7Xq LFmw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=Th9symoIAedk8n4yZ9NYso7peFhQUZDzMX3JzdaOdRI=; b=3efR1/pFoid4RIljT3PF0OMnv90OJwLsrbfhR58EqqlYTqIqUmX88ZZBkUZGf3Xsot J7ML1qYXAecdfjfelnH1hnhDxwnOn4OdPC4yfFUUHT7BlgabS78EsVXxOA37RIwJZEis x6Ak5BfsP5Js77TmIFvr6xAFmhGEcMT7fiASWPiTqoqWOmgwB7mtuKmdzFt3wJnqZLZF 4a7ianBwGm6VJl1M25HjYOLG4P75tpcekyl9RqcwyaZP9AOSDDpWUAG0+FrsvjF9050n huiQEn9gOn68b1Sv1S9woKJWCEXJdVpVnG2JhzYt05fk99zOIXYqcBp280WRDiLv8Ffz Arhw== X-Gm-Message-State: AJIora9GbFyhEHt+c4MuzL9Cz7SQBU5RVMlxU9W9E6+D28WjOZGD+ofj Q+Bn1VAd534tpx6ntRfTZiKUR6iZyYuKCA== X-Google-Smtp-Source: AGRyM1sRFItr5K97WutZ4+jC3B/HZWY5O673r84eJzLkSRDK2hVFV6aCcf+A5MhGwBjL07PkeH4iZw== X-Received: by 2002:a17:907:2cca:b0:72b:4188:f95b with SMTP id hg10-20020a1709072cca00b0072b4188f95bmr16625717ejc.153.1657642144330; Tue, 12 Jul 2022 09:09:04 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.03 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:03 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 1/7] libsepol/tests: add ebitmap tests Date: Tue, 12 Jul 2022 18:08:52 +0200 Message-Id: <20220712160858.22677-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 --- 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 +#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; + + 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 + +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 12 16:08:53 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: 12915279 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 DBD49C43334 for ; Tue, 12 Jul 2022 16:09:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234238AbiGLQJP (ORCPT ); Tue, 12 Jul 2022 12:09:15 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52510 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234228AbiGLQJI (ORCPT ); Tue, 12 Jul 2022 12:09:08 -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 65E0C2316C for ; Tue, 12 Jul 2022 09:09:06 -0700 (PDT) Received: by mail-ed1-x52f.google.com with SMTP id eq6so10734096edb.6 for ; Tue, 12 Jul 2022 09:09:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=0W9B5X+a7rqKPu7imnEnZRKOX7qiw8f6dz5BGNPo/5Q=; b=GZRL0In2IGOzRPKdY3TYo6wy7l/971tqvk/G8mICVvdVkiPISFaHvj+adhlc88Kkfw /PW1OzBuiVBBYT0Ntj+PMiBmGGNnsK3dpbe3/hVsIJPzmu/+MYEeURqUTseWsGVVfe/8 z6qdAjh+UKQRj2wI1ym3mG5xtgryLf8ZPOVdBMPM7O2xA9it6/2JbnKJ76FuFvkQUp1V ZF8o73mx+c16KEQdmHhYI5dVyj/k8vKFEnBoYov/L5FCti/Si8ehUr8aNNHsU+jp76Ou 67hzwdjOU+eftMl6OS+1qE0jSOscy593CIgvRIhjvLf9eDdW9YwuJW+vy5sk1q0+/O/n hOJA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=0W9B5X+a7rqKPu7imnEnZRKOX7qiw8f6dz5BGNPo/5Q=; b=NMgTgiRsbxXC49YHqsAGiujDlzCwF2y0He06wm7O0TyhFB7/q3XqxNIpDCeFLQhXMw clWc8sxV/Ww18I1c4ack0hSz4pAEhQQkb8UYRX/Qfbg7s1bCLZzH/lrcrHcWVz+Exh0s 1TrShaLODMLSZAy92LldoOgDOsYP5Pfu1F3giGZKOkH22v8JXmCzw+Xza6VODaos5Mwh L+JZRfwf351Ygw9rtGxg9P2PB3DFScq+Vl1SuO4Cnce9N2TvmE7Fu7y3nkwPndMx5I/g BZ97spokZqjrkpC/AaTuPqCOv5VJ1H8pjZWAE4pM8XYd8Zlrg86m98eRUwMxVwZ77RGq ev4w== X-Gm-Message-State: AJIora+4l32StlWPptuAJNi8zr5gRM269nDzBprhvq2xMnsQYBTT3NAy DsyoAcXoCa4R6Qzu9p/+UiJLwkpMouwgnw== X-Google-Smtp-Source: AGRyM1u1tUxZOcwZnkpPU78HlpapJOms+L/itxKFYtSk5LPVY+ExbSfiGMoVL9ZrZdcbN/KBIGHl6A== X-Received: by 2002:a05:6402:5412:b0:435:5997:ccb5 with SMTP id ev18-20020a056402541200b004355997ccb5mr32041473edb.167.1657642144964; Tue, 12 Jul 2022 09:09:04 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.04 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:04 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 2/7] libsepol: add ebitmap_init_range Date: Tue, 12 Jul 2022 18:08:53 +0200 Message-Id: <20220712160858.22677-2-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220712160858.22677-1-cgzones@googlemail.com> References: <20220712160858.22677-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 --- 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); From patchwork Tue Jul 12 16:08:54 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: 12915278 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 7FDC4C433EF for ; Tue, 12 Jul 2022 16:09:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229760AbiGLQJO (ORCPT ); Tue, 12 Jul 2022 12:09:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52512 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234238AbiGLQJI (ORCPT ); Tue, 12 Jul 2022 12:09:08 -0400 Received: from mail-ej1-x62a.google.com (mail-ej1-x62a.google.com [IPv6:2a00:1450:4864:20::62a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F0E012625 for ; Tue, 12 Jul 2022 09:09:06 -0700 (PDT) Received: by mail-ej1-x62a.google.com with SMTP id l23so15162692ejr.5 for ; Tue, 12 Jul 2022 09:09:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=zWHpdd1Gp2i82c79opTYMnv9mwhyMyNRPmGXCJAnIZ0=; b=E962jEg21N5C9b499FqfGZTds7yFj45Whqk/O0RePud1iOoCE0MJdlYI27/bAYASb/ VJ30DO+CghJDhnxtGxtUY5uLK1FESfTfqojJf0Ijf6GFhlfcnTbSDnIq6xTPG1TLKHjv s3/Oq18BQwU2rX4jkvKYEQSMl8eHIoWTxcHN8o/LoyLgzX5SJc2e3dFLLPRwGZJkon65 Lmyu6GRu2guNlL/wRL4RxTzFxLLnh+16RVPg13epsSO2QqaNHQhHU9zfe+8Cau85MxWB h4xQ30AKoloT9uvHOzi5lenvgsTXBzhOIEPtHxWD4gmwGUXq9UV3D6CIkGEgagBb3/aP 23/w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=zWHpdd1Gp2i82c79opTYMnv9mwhyMyNRPmGXCJAnIZ0=; b=KDR/0MGr6psDszGKwgGJh5JfByH1l0BKlqICWqOsp39fpJn7U9aTUuyOPRN2ZEmvAr C0rSdSMtB13370xNv0+nVPTiJ/DrmNeGo9YeY3HUAKrdAKCrVERCkDQRvfz03HVknGpS 9zPvViLdQOgEJEd1zMSFoa+Et2lt9ufh8MDpyihMkhS4rjL+TiAJQcQ7tZ6Toq/GM+ce jZ8bGoxYYknUY90On6m8cFAq+O/CPBaRT4dq+vyq8pWrBCHHUMKCF2NF3D6RrwC8GYVZ wFKYsbFhMXluSAtRB/W2vQyykzki1FUc5ACfF/iuDeDVIsoTmnf50OSR+VtcS1CFj5U7 KFpQ== X-Gm-Message-State: AJIora9yrJ3xh5we87tLLAhr1T6pBdJMc9hhtsxnXgUJC+fTHwkKJJP3 MrCV8jc8AQVGPNljLKKUAz5c3WmuDQrABQ== X-Google-Smtp-Source: AGRyM1sv404SnU6RHdiGbtvpQsXe3iQmr7GXT9cyZgKFi825UMuu9uxwKlQI7dKaYIalCPwYd46e9w== X-Received: by 2002:a17:907:2d8a:b0:722:e35b:695 with SMTP id gt10-20020a1709072d8a00b00722e35b0695mr25438635ejc.470.1657642145502; Tue, 12 Jul 2022 09:09:05 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.05 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:05 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 3/7] libsepol/cil: use ebitmap_init_range Date: Tue, 12 Jul 2022 18:08:54 +0200 Message-Id: <20220712160858.22677-3-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220712160858.22677-1-cgzones@googlemail.com> References: <20220712160858.22677-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 Acked-by: James Carter --- 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 12 16:08:55 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: 12915281 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 7963CC433EF for ; Tue, 12 Jul 2022 16:09:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234264AbiGLQJR (ORCPT ); Tue, 12 Jul 2022 12:09:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52514 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234240AbiGLQJI (ORCPT ); Tue, 12 Jul 2022 12:09:08 -0400 Received: from mail-ed1-x52c.google.com (mail-ed1-x52c.google.com [IPv6:2a00:1450:4864:20::52c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7705127FD3 for ; Tue, 12 Jul 2022 09:09:07 -0700 (PDT) Received: by mail-ed1-x52c.google.com with SMTP id r18so10714486edb.9 for ; Tue, 12 Jul 2022 09:09:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=6i9iU/qgXKqe/f/E8m+XyaPz1V6XYcq7ck58+zDr220=; b=j68Ksh6ior9qeiCMNaFVMlsS9AOOao3YWAkxhO4nh1aLbjJVnw78s7ByA8hEyfn1Ed 6k0PBX3dkHVwbn5afeAbnAcd+p/vmYBdGLoEkn3f6oJIA35fMiD1IJTmK6xjH6StNU71 3GvQUxdQl9PxZXyDOnzrPdGodXelvMylZ3gwREL050nNPuoCUZmvwg92FHYVuY5Hy+W7 X1dPaM1kc2mTCwfArOZVpWY9bbbQUhu6KYBIOXq16P+Dx/AieRoila7uiH46ExoKSQwO fIEWXQOmYo93rwOaxb5pUD1OB6hcDFq/JsrjG7atgAjRBS6AOEgK26x/aPYY24NJ8YQh Hi/w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=6i9iU/qgXKqe/f/E8m+XyaPz1V6XYcq7ck58+zDr220=; b=kX6k2SscBV+DpxAAyegVo5aA+KXV2TFAKgKPWjjRzCbHFLq9SdC2ObBaCqVQtpDUNY G1UGHL131LkaPXF59lAB+I0dGrC/UJ01CnqGaYZblHtntzmyHe9ziuMJJ28rHjncfT9h hMNsAkaBOtREpbOyCPWAuxYyz5NQDukyoQ64Ki30jrwiwYmf8bl9ogxweDQ27vhv02C5 m8VszpNc2N3/6UUHQOPYwsaYtz3Oyvpk1+JIVszIlwd/a2qm0V26EwHGnTToR6WgRT71 i5GuoL0GblsZ/zMlkeHdRAWDee82xPKTHh8Yu9Ql2sIKF+LNZb9MAOmPDM/i8kbd2PCc ivAA== X-Gm-Message-State: AJIora8KDac2EQIB2b+Po5B9hrmu9RzIh4704VGyCG6WLIoHCgpUi/4j Rx0grWtH/06s8C1+4NypQnWPmBdD1SiAiA== X-Google-Smtp-Source: AGRyM1t/pQN2EEOTOA7QindNtxd9EZvL2jv+mAOdWZqDYZRcU8lUkANl3OvF9a+uSCTWJB61bKHX+g== X-Received: by 2002:a05:6402:228f:b0:43a:896:e4f0 with SMTP id cw15-20020a056402228f00b0043a0896e4f0mr32087123edb.81.1657642146036; Tue, 12 Jul 2022 09:09:06 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.05 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:05 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 4/7] libsepol: optimize ebitmap_not Date: Tue, 12 Jul 2022 18:08:55 +0200 Message-Id: <20220712160858.22677-4-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220712160858.22677-1-cgzones@googlemail.com> References: <20220712160858.22677-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 Acked-by: James Carter --- 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; } From patchwork Tue Jul 12 16:08:56 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: 12915280 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 9EE3ECCA47C for ; Tue, 12 Jul 2022 16:09:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234245AbiGLQJR (ORCPT ); Tue, 12 Jul 2022 12:09:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52524 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234247AbiGLQJJ (ORCPT ); Tue, 12 Jul 2022 12:09:09 -0400 Received: from mail-ej1-x62e.google.com (mail-ej1-x62e.google.com [IPv6:2a00:1450:4864:20::62e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0A27D12D2F for ; Tue, 12 Jul 2022 09:09:08 -0700 (PDT) Received: by mail-ej1-x62e.google.com with SMTP id l23so15162788ejr.5 for ; Tue, 12 Jul 2022 09:09:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=KWFaMKkeTX17vWaSfNfz/271fEVh8cMtoLZ4z8S3Jx4=; b=fLcJ1m4nNv8gZ7N3qf8XZBQujtQk9hgp8tJNt6f0PASQI6hkpRS2P12nEVtCdje/af yc0CmFTRN/CukgyXw7BXh7/pFt0cg/YPEt/3LgdVWJFCfpnz7EATJjhsYeSJ+PzhBcgV 8twqlAO0QT1h+bC1DodH+94P6pp1X/mK/bOlhImNSs7b52f0uKXctDJhYRZsTTjMWKjE wF029lrvPjBeMuqCZ9lEQY4dCXzgYjvKnQLFUdzWo6SsW9Si7zN9Q+sNBamE6K6ccxS4 JemHsMBEja7ylnl4Xi/AS3g68MaKjBRsSOBTJ0tqyHCNIDoQCxSdzICLPvNsQlqBO7hX o2qA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=KWFaMKkeTX17vWaSfNfz/271fEVh8cMtoLZ4z8S3Jx4=; b=c5Br/fp+b7BawIzI8ioUKJRZ68Gfln4CyJdloMKc5QxbhzpGS7jAQaALoCDDNGfqmZ rsYhx7OdVYUSr8q5IKAHJyrPW7KcmcfYEM4HPvdps4TiSF7s/z++crNdonn2lcWl/A3i npOqX99q5gTze9rycoBgtI4E4gq3+21QqHIn1yHW2GIY8Z18PfjZKfxkUheAUpW8Fbxc T4hSg4xR84gu4fwbBsv6Sxe4/CZQSKzkcw0A0kVnbfDMnkmdTsAp25AnsAOjhCpW/pyp HOO5NBdSM92S5rxzaqAh452v/REP6RCg60KodrfFG/7eJ8AiKDcMzdL9WcRuQ76ZF62l NRwQ== X-Gm-Message-State: AJIora+qApYdO7jNFgftHRxe5wislIYnWM+KLpphLGoxOzm0e2M+tIMx i3zXTfQJuKBsxloZ1ucsz2ukgPgXg0Fh/g== X-Google-Smtp-Source: AGRyM1ut6BDqhGpX/481ErKRi/JTFt5cqyDNWyAyccsRWrU1BpS1WwVC4YDk50FCK2Xmx/0XcaG8dw== X-Received: by 2002:a17:907:a074:b0:72b:5851:361b with SMTP id ia20-20020a170907a07400b0072b5851361bmr10274999ejc.310.1657642146573; Tue, 12 Jul 2022 09:09:06 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:06 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 5/7] libsepol: optimize ebitmap_and Date: Tue, 12 Jul 2022 18:08:56 +0200 Message-Id: <20220712160858.22677-5-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220712160858.22677-1-cgzones@googlemail.com> References: <20220712160858.22677-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 | 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; } From patchwork Tue Jul 12 16:08:57 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: 12915284 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 4C048CCA483 for ; Tue, 12 Jul 2022 16:09:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234247AbiGLQJS (ORCPT ); Tue, 12 Jul 2022 12:09:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52540 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234256AbiGLQJJ (ORCPT ); Tue, 12 Jul 2022 12:09:09 -0400 Received: from mail-ed1-x52b.google.com (mail-ed1-x52b.google.com [IPv6:2a00:1450:4864:20::52b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 93FE02625 for ; Tue, 12 Jul 2022 09:09:08 -0700 (PDT) Received: by mail-ed1-x52b.google.com with SMTP id fd6so10713311edb.5 for ; Tue, 12 Jul 2022 09:09:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=CAWUvuH2vtDhqU49owxtq8l4iLBUVe5BvEM74A+7J58=; b=ihzDE9ZDUa8Rv4WAGGJAZHJP/X2olFgES+L0/REfLv0Yfo4azjSCIKwexv5VbzqXpw 7Fk507AELQz15VFcJEQq3D99DbiuxPTMWaOK/lC3lJKs8x0goosXuMbhsKfNMREJ648A Q8S3yNSDEr2heQeDDiUcczkCYxgpCc2O9EujazCasQHbZU/zEUpjiyHtRQPtftYAWRv9 WeiQtQKBm0h6ARK8kW65HyIKAjUL4MdmEe2pSIgy4YpOpIn8EtqWiy4M0EqjTRn0H05d db7jIl5FyHxlsvyFozRgY+ENIZsUgV32pZHYsf2zHuarLNfVRE+gPx2W/2toeAcahRMQ 0aWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=CAWUvuH2vtDhqU49owxtq8l4iLBUVe5BvEM74A+7J58=; b=v1hCSPbUGuFGew3WqEGq1lm/sEpL6b1V0ACdtiPg3mLPU3ODyMh1YjL1SQnmkDAp1y NWVWQjpEwNLIABNeDO9xCkEELdQ23K+LX44StNj7UkSFFwha1vTcray5IbHfvO6BgO6M W+gp8UEqGx6PN7Z5oY8Ko3xDUZGWjQC1oCI7UF9rJb0JHTmdIpgRdDo9GPTgrlzqTG+K giUD7xsPio857U3YuHMYrczruMkwBxpLCMr3aW+w5OjiUb6BRxTXaPVBQKXbwFtFXqqw LwVFQ/hx0yCBwxqz0d3FSUjliVjOt28Jl0gFE2SCYATtCEdUWP+2KJ0g0KMC6xAVlcju QQVw== X-Gm-Message-State: AJIora9ulhUczzLDDqVO2AYRCsHoAtkazn4xB7lJgm8H4roSVhiGNaVI A3CLHB9Doyz2it1vClDGLVeWdb98ZkoLZw== X-Google-Smtp-Source: AGRyM1ur4U/tMvTNIEa5TIdQkRMwx8ddFqT6R2nxqo5rH5JHiaI6yGKZ7WGfb83OVNUob9kLxw7JYQ== X-Received: by 2002:a05:6402:909:b0:435:a8b:5232 with SMTP id g9-20020a056402090900b004350a8b5232mr32659034edz.240.1657642147114; Tue, 12 Jul 2022 09:09:07 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:06 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 6/7] libsepol: optimize ebitmap_xor Date: Tue, 12 Jul 2022 18:08:57 +0200 Message-Id: <20220712160858.22677-6-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220712160858.22677-1-cgzones@googlemail.com> References: <20220712160858.22677-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 Acked-by: James Carter --- 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; } From patchwork Tue Jul 12 16:08:58 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: 12915282 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 E2F47CCA482 for ; Tue, 12 Jul 2022 16:09:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234240AbiGLQJS (ORCPT ); Tue, 12 Jul 2022 12:09:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52520 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234266AbiGLQJK (ORCPT ); Tue, 12 Jul 2022 12:09:10 -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 50E5427FEE for ; Tue, 12 Jul 2022 09:09:09 -0700 (PDT) Received: by mail-ed1-x52e.google.com with SMTP id x91so10736395ede.1 for ; Tue, 12 Jul 2022 09:09:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references:mime-version :content-transfer-encoding; bh=Vk5+pyuzjefxFiWp65Xv/Z+qbOCjYTIjYInRaaxVfts=; b=PjF1jh+QqyY5WOmra8Mw863m4IJnTJXJPKj/SSCsG98ugvA09EhhZB4LGVY+vHcMaj GynHVHoVzRPu29zzHnBGS9Iol4qcPv+iEW12kHOVSRZKXmdC5J9IpH/KvcOhYYk74FEt eJxtJqcKqGRq8BdjQ01l4oMN+ELKNzYpJjDxU7lFx/Lquiuvd8rChcQWSMp08p6AK+4f pr4NJduINqxv9NrDfw4h5HaEvtvhFRW61gMSJS7xLpaddO0cK8p7RrKKcsk3XouGbmce 1DRbacfcjO1D8Aj2vyy4RtpNCWI6JprpI30RNeBTHaGBs7OPI+KSsFSBDhrX8nJtnQmn 6rqw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=Vk5+pyuzjefxFiWp65Xv/Z+qbOCjYTIjYInRaaxVfts=; b=3zeaz/X7Zpym07BOCWnEqJOzlTvE1j2drJREYEZAnZUSAyc1cvmP3adlltoYSMq9yn i1VRXjk3YcoyUmwXbXnPnDMh2IDU8pG+ShKyX08UbsfRxL0tuMjPig2kUfja/u9KzE9W NTjB2OVY2Wx0/Drsv6zHmq91A2dPUytR/Yklv2jR2ekvjbkIIKl06CH9wa9sIVTIYm0T 2pK90VBNdZF3lV7xHSMoQouy9OVSktmLNyrStoMFM+PVZaqzMA6T99KVC0gPEt+Aaf9L Jdt7jgM+N8YxiKrqFfqhj0C5ixUty8jjHc9d3L22Vm07daD0D46Aj1QQw0LtKJ7sZ7we d6ZA== X-Gm-Message-State: AJIora++gNVh7H1xbChJoznHMZ1shxDb3OredS77HP6vPh62wkcUcXlj 52p2G6gAnali92rn2ybhRtyVrzgxYMQlGA== X-Google-Smtp-Source: AGRyM1vPQERbBoVbncri0KBrt7uE8s15EHRoEtUXm3VBEtGbHSp6o/NMpyQ3jYn7I18YxWpZuhJUNA== X-Received: by 2002:a05:6402:270d:b0:43a:d1e8:460b with SMTP id y13-20020a056402270d00b0043ad1e8460bmr16464192edd.40.1657642147885; Tue, 12 Jul 2022 09:09:07 -0700 (PDT) Received: from debianHome.localdomain (dynamic-077-010-190-079.77.10.pool.telefonica.de. [77.10.190.79]) by smtp.gmail.com with ESMTPSA id p13-20020a17090653cd00b006fed85c1a8fsm3887127ejo.202.2022.07.12.09.09.07 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 12 Jul 2022 09:09:07 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 7/7] libsepol: skip superfluous memset calls in ebitmap operations Date: Tue, 12 Jul 2022 18:08:58 +0200 Message-Id: <20220712160858.22677-7-cgzones@googlemail.com> X-Mailer: git-send-email 2.36.1 In-Reply-To: <20220712160858.22677-1-cgzones@googlemail.com> References: <20220712160858.22677-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 Acked-by: James Carter --- 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));