From patchwork Fri Aug 18 15:12:18 2023 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: 13357929 X-Patchwork-Delegate: paul@paul-moore.com 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 64730C71155 for ; Fri, 18 Aug 2023 15:13:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1378019AbjHRPNE (ORCPT ); Fri, 18 Aug 2023 11:13:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59384 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1378106AbjHRPMu (ORCPT ); Fri, 18 Aug 2023 11:12:50 -0400 Received: from mail-lj1-x236.google.com (mail-lj1-x236.google.com [IPv6:2a00:1450:4864:20::236]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 197864691; Fri, 18 Aug 2023 08:12:38 -0700 (PDT) Received: by mail-lj1-x236.google.com with SMTP id 38308e7fff4ca-2b9fa64db41so17195911fa.1; Fri, 18 Aug 2023 08:12:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692371556; x=1692976356; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Nrjf0t8/+tWorDt5ATsu0uwkTQCJ3AKC0mV+zReeAks=; b=C6aXLHqXPydc67rzEejZehoy1UgVUKujAoxb7mHuAy8TuIaaqkLYGDAl6/SlUrlZVv F+6Ki8z5pVgTaj0GdcVBVcbpY87iVFlePwbYTyLRpYo160fag1pAYHbfaLzPwQVOMJBO QUMzXK8GFLBlFIzmAeTGz6lEB6jaTI3cAriCxIHy0L9eBjkEmohn2DfsDu0R/FBTSSOa 8B8TllObHGwdhg7+XYA3nIieg1sp1aUqxz9Q5YW97WmDs3AlDhxzqnZgJ4+aQU57OOow /awE7TPAUhMEOSsoAjhhKssoyFX+N9fLEZ6j0NaIR6PCPhAsNfAIew19EVomv0oGuLPn m6cQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692371556; x=1692976356; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Nrjf0t8/+tWorDt5ATsu0uwkTQCJ3AKC0mV+zReeAks=; b=XbjcK64PmaTW+TCxTMmOBGVwdKIg+RRoDdqxagWmIfuRCQitLIjRdUlYDwFotK/MuX xdnX666dAexY37/PDcx/RQMaLk2Jd48NZWujotjEovMZzFYXLsN1H0DqYQbonUkgDvNA V/Je1MobAZDmThzkZse9cPz5RS+hr/oqicSBh8qdy3spaRHI+Oh8fzgqsLJuXQMiN2oB K2SzV66InoDrnhgGQTlzMVj9GuweYyxXadsMcgeK36ct7lBlwv0XpWZnEsB0jg+untqz 2hIHp04GnK+BL+TXWkMBZZw0juRqNegwp9M0EfpKabUAEeD2qom0N8ByX+cVYTGd1TLX Es9Q== X-Gm-Message-State: AOJu0Yy7L3/aAZiPjdHxsu7+v0emM6v0+wLZTOjh+WCPGVhFksU80cG3 AJiaYg6e2ic2+YdpdwjNL674akD8051txQ== X-Google-Smtp-Source: AGHT+IF5HJOYkcnwtOi2QbJfJiI7iE60S+GXRtNvGBLqt7zvaC2ojE2nlEQhzztp7oyjFgI5oWaYIw== X-Received: by 2002:a2e:9283:0:b0:2b6:d603:7667 with SMTP id d3-20020a2e9283000000b002b6d6037667mr1793342ljh.8.1692371555528; Fri, 18 Aug 2023 08:12:35 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-095-116-071-217.95.116.pool.telefonica.de. [95.116.71.217]) by smtp.gmail.com with ESMTPSA id sa19-20020a170906edb300b0099ca4f61a8bsm1285913ejb.92.2023.08.18.08.12.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Aug 2023 08:12:35 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: Paul Moore , Stephen Smalley , Eric Paris , Ondrej Mosnacek , linux-kernel@vger.kernel.org Subject: [PATCH 1/6] selinux: print sum of chain lengths^2 for hash tables Date: Fri, 18 Aug 2023 17:12:18 +0200 Message-Id: <20230818151220.166215-6-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230818151220.166215-1-cgzones@googlemail.com> References: <20230818151220.166215-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Print the sum of chain lengths squared as a metric for hash tables to provide more insights, similar to avtabs. While on it add a comma in the avtab message to improve readability of the output. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley --- security/selinux/ss/avtab.c | 2 +- security/selinux/ss/hashtab.c | 5 +++++ security/selinux/ss/hashtab.h | 1 + security/selinux/ss/policydb.c | 4 ++-- 4 files changed, 9 insertions(+), 3 deletions(-) diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 86d98a8e291b..955cfe495606 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -349,7 +349,7 @@ void avtab_hash_eval(struct avtab *h, const char *tag) } pr_debug("SELinux: %s: %d entries and %d/%d buckets used, " - "longest chain length %d sum of chain length^2 %llu\n", + "longest chain length %d, sum of chain length^2 %llu\n", tag, h->nel, slots_used, h->nslot, max_chain_len, chain2_len_sum); } diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c index ac5cdddfbf78..c05d8346a94a 100644 --- a/security/selinux/ss/hashtab.c +++ b/security/selinux/ss/hashtab.c @@ -107,10 +107,12 @@ int hashtab_map(struct hashtab *h, void hashtab_stat(struct hashtab *h, struct hashtab_info *info) { u32 i, chain_len, slots_used, max_chain_len; + u64 chain2_len_sum; struct hashtab_node *cur; slots_used = 0; max_chain_len = 0; + chain2_len_sum = 0; for (i = 0; i < h->size; i++) { cur = h->htable[i]; if (cur) { @@ -123,11 +125,14 @@ void hashtab_stat(struct hashtab *h, struct hashtab_info *info) if (chain_len > max_chain_len) max_chain_len = chain_len; + + chain2_len_sum += (u64)chain_len * chain_len; } } info->slots_used = slots_used; info->max_chain_len = max_chain_len; + info->chain2_len_sum = chain2_len_sum; } #endif /* CONFIG_SECURITY_SELINUX_DEBUG */ diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h index f9713b56d3d0..09b0a3744937 100644 --- a/security/selinux/ss/hashtab.h +++ b/security/selinux/ss/hashtab.h @@ -38,6 +38,7 @@ struct hashtab { struct hashtab_info { u32 slots_used; u32 max_chain_len; + u64 chain2_len_sum; }; /* diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 28bd75dc6f71..84f02d4f8093 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -684,9 +684,9 @@ static void hash_eval(struct hashtab *h, const char *hash_name) struct hashtab_info info; hashtab_stat(h, &info); - pr_debug("SELinux: %s: %d entries and %d/%d buckets used, longest chain length %d\n", + pr_debug("SELinux: %s: %d entries and %d/%d buckets used, longest chain length %d, sum of chain length^2 %llu\n", hash_name, h->nel, info.slots_used, h->size, - info.max_chain_len); + info.max_chain_len, info.chain2_len_sum); } static void symtab_hash_eval(struct symtab *s) From patchwork Fri Aug 18 15:12:13 2023 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: 13357931 X-Patchwork-Delegate: paul@paul-moore.com 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 3E63BC77B7A for ; Fri, 18 Aug 2023 15:13:37 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1377993AbjHRPND (ORCPT ); Fri, 18 Aug 2023 11:13:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34704 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1378071AbjHRPMo (ORCPT ); Fri, 18 Aug 2023 11:12:44 -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 24055420C; Fri, 18 Aug 2023 08:12:27 -0700 (PDT) Received: by mail-ej1-x630.google.com with SMTP id a640c23a62f3a-99bf8e5ab39so133932566b.2; Fri, 18 Aug 2023 08:12:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692371545; x=1692976345; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=rmwLesiFYumNQ6O67fwcKZ7FMnVzuOPHn3ALA9q8Gkg=; b=bWv9yL6kAXBMtiAE5R3Vf0Ub8ZGiElyEL7Odw7Z3/0+CCMfc6Ym2nt0TFzS4q91NGe T/vzJY8OOdNIzWtoVmFSog2rI/VfXGhHW5ziEC4FkrvI1uxZ67Pew0SkAeTRxZ59CGR3 h0LJeU3dxCbNKIFIKicCLI3SM2SvGwbPXQBL4DDtkHuUTXj07MvqJ6x9y791lW9K/U1Q 9b7rQSOw86thqXaEhTTgHE5gCIwWFDNO87zSn9jBqXOzDDYTC8rWPUiGmPHbXI3c/j+F ZQz517p0R9VCw+6nuf4/yIbRQIiMrSROOoNZM9CXNFmCKDrfvY01w1iA5iaO6Fsc6If7 PVgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692371545; x=1692976345; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=rmwLesiFYumNQ6O67fwcKZ7FMnVzuOPHn3ALA9q8Gkg=; b=VbEwUDFkOl+bH6g1sX0PseY0wPEVbznpU+fwSL9YGmCM1ht7rh03jSMx8eVQY1bpdo v0wNhjkO3YggPKG9/2sYtmVsM2B3LCNdVAk/SJXsAGqTm+stLnV69qL8fIs3D/wNUQ+g 51ZjQkhCIVQOqaBIUpFNvrsONGXmqiekE1LjgNdKfPJnSqIV+WorDvTJP0yZbmzKPQRe QzaVF4r0G1vWkOCesBH4xVqGQJ1afoPCCRV4KBw45HdXpWbgXZwCag2VDhk0ZmHEFyvX Eth1k8bIls2ZF/1/fZYH8EpTNeTAeayP0+WiJ/nI01tyJY5yVvl21w1QE3qySpo5YpBe lFHQ== X-Gm-Message-State: AOJu0Yz3KJ4dG92XDTnMTMVx4zjUS3f9R0p30tcf7O/S4Onhtg08QKRB tHz6VL6w2773QE5cYbyITy+/a/7fTEh8aQ== X-Google-Smtp-Source: AGHT+IFJ1Hdu25ZB09hgePICL8nmS6b458AH2wdxKHHueAU4N5ZIFOtwjnnZ06Wph1T+T/fjT9+rpA== X-Received: by 2002:a17:906:3099:b0:974:1ef7:1e88 with SMTP id 25-20020a170906309900b009741ef71e88mr2205288ejv.13.1692371545323; Fri, 18 Aug 2023 08:12:25 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-095-116-071-217.95.116.pool.telefonica.de. [95.116.71.217]) by smtp.gmail.com with ESMTPSA id sa19-20020a170906edb300b0099ca4f61a8bsm1285913ejb.92.2023.08.18.08.12.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Aug 2023 08:12:25 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: Paul Moore , Stephen Smalley , Eric Paris , Ondrej Mosnacek , linux-kernel@vger.kernel.org Subject: [PATCH 2/6] selinux: dump statistics for more hash tables Date: Fri, 18 Aug 2023 17:12:13 +0200 Message-Id: <20230818151220.166215-1-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Dump in the SELinux debug configuration the statistics for the conditional rules avtab, the role transition, and class and common permission hash tables. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley --- security/selinux/ss/conditional.c | 3 +++ security/selinux/ss/policydb.c | 6 ++++++ 2 files changed, 9 insertions(+) diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c index 81ff676f209a..0dd17fe76286 100644 --- a/security/selinux/ss/conditional.c +++ b/security/selinux/ss/conditional.c @@ -171,6 +171,9 @@ int cond_init_bool_indexes(struct policydb *p) GFP_KERNEL); if (!p->bool_val_to_struct) return -ENOMEM; + + avtab_hash_eval(&p->te_cond_avtab, "conditional_rules"); + return 0; } diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 84f02d4f8093..932e383bcad6 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -1158,6 +1158,8 @@ static int common_read(struct policydb *p, struct symtab *s, void *fp) goto bad; } + hash_eval(&comdatum->permissions.table, "common_permissions"); + rc = symtab_insert(s, key, comdatum); if (rc) goto bad; @@ -1339,6 +1341,8 @@ static int class_read(struct policydb *p, struct symtab *s, void *fp) goto bad; } + hash_eval(&cladatum->permissions.table, "class_permissions"); + rc = read_cons_helper(p, &cladatum->constraints, ncons, 0, fp); if (rc) goto bad; @@ -2616,6 +2620,8 @@ int policydb_read(struct policydb *p, void *fp) rtd = NULL; } + hash_eval(&p->role_tr, "roletr"); + rc = next_entry(buf, fp, sizeof(u32)); if (rc) goto bad; From patchwork Fri Aug 18 15:12:14 2023 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: 13357933 X-Patchwork-Delegate: paul@paul-moore.com 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 EDE6BC7EE2D for ; Fri, 18 Aug 2023 15:13:37 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1378030AbjHRPNE (ORCPT ); Fri, 18 Aug 2023 11:13:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58640 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1378072AbjHRPMp (ORCPT ); Fri, 18 Aug 2023 11:12:45 -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 242D6420F; Fri, 18 Aug 2023 08:12:29 -0700 (PDT) Received: by mail-ej1-x630.google.com with SMTP id a640c23a62f3a-99c47ef365cso136754466b.0; Fri, 18 Aug 2023 08:12:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692371547; x=1692976347; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=aZnmcLyRXXMZRHPXrv6ePuzpP+/82gvSRdg+zxUbEoY=; b=PR6E/gu5dWaAGyXOLnmhr0dRrUQhWYq4G4mzcZDo6w4A5ZQo1LzuAqJh0orL5nMZGU CqMLt8bjwvOc/sRD0auPZ7jwc67DB5DmFMAueyJJUW6G2sp9gZHm1ZpDXT65CYvoWOZL E99LnOjVDA7+ZkvC6hcyZpMqTnbkmwh50V9l8t0tlC3PRWzFxslZeg6Aw6fzq3TkSumU EHkcjI0JFQo6oo9MwSQQp/ckZFmypzYOlU0GRxeG0cpneHRX1Am893WIjEGyQ0snW/b5 xeDDq8L6SLE37QIf/7vy+G5GRid7LPsjYCvWlNYbKoQnJUAuLEHfWidU/lCoCbvcaLgL HHng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692371547; x=1692976347; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=aZnmcLyRXXMZRHPXrv6ePuzpP+/82gvSRdg+zxUbEoY=; b=KtdQrs+mZlKXtZ+h0iMQQH6GAYaeQ2QrNB1CQZlgQ0637peFlFpar19xGZCbh07ZuN iyIbBhNO60L/h6rvGLo9LccQQ3C7KZnXVA51CgC0sNtuq2iKqitwGEo6NuiFXA6lPMEu +AAujJeJJr94G/cgg7SsXaJzqhB0BX/IZORzZ30E9rV/2SWpJdEUZV/5Dla0l25D3nOp yUMhEW5ew4A9zSiW9GpJurVeL9zPytRZiCObOfrnshVUL12p1PTfQoNnVjrDWK6Jcuks dpX1fqmvgiQiTLgeSANWhjzLIkwZiibmOcdkMNSlsCBEgZNWZfAvanDHsn82bS8FyKTh kBJw== X-Gm-Message-State: AOJu0Yy/6Qarv6NIvAOaPbqvNHR+KnxErQ5VJLYKMjl2Bl6/rfzwsdkL KqqIQud7IhvZL8/KE9VddydDn3CNR/p0xA== X-Google-Smtp-Source: AGHT+IG8jWZ6cYQXclRyWxtIZ9h6mMLk3fFHxvoLhY9num9K8nCMXsx7+gnX543S9aZ9GZDWfVBamw== X-Received: by 2002:a17:906:74d7:b0:994:56d3:8a42 with SMTP id z23-20020a17090674d700b0099456d38a42mr2235318ejl.27.1692371547308; Fri, 18 Aug 2023 08:12:27 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-095-116-071-217.95.116.pool.telefonica.de. [95.116.71.217]) by smtp.gmail.com with ESMTPSA id sa19-20020a170906edb300b0099ca4f61a8bsm1285913ejb.92.2023.08.18.08.12.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Aug 2023 08:12:27 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: Paul Moore , Stephen Smalley , Eric Paris , Ondrej Mosnacek , linux-kernel@vger.kernel.org Subject: [PATCH 3/6] selinux: improve debug configuration Date: Fri, 18 Aug 2023 17:12:14 +0200 Message-Id: <20230818151220.166215-2-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230818151220.166215-1-cgzones@googlemail.com> References: <20230818151220.166215-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org If the SELinux debug configuration is enabled define the macro DEBUG such that pr_debug() calls are always enabled, regardless of CONFIG_DYNAMIC_DEBUG, since those message are the main reason for this configuration in the first place. Mention example usage in case CONFIG_DYNAMIC_DEBUG is enabled in the help section of the configuration. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley --- security/selinux/Kconfig | 10 ++++++++++ security/selinux/Makefile | 2 ++ 2 files changed, 12 insertions(+) diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig index d30348fbe0df..61abc1e094a8 100644 --- a/security/selinux/Kconfig +++ b/security/selinux/Kconfig @@ -77,3 +77,13 @@ config SECURITY_SELINUX_DEBUG This enables debugging code designed to help SELinux kernel developers, unless you know what this does in the kernel code you should leave this disabled. + + To fine control the messages to be printed enable + CONFIG_DYNAMIC_DEBUG and see + Documentation/admin-guide/dynamic-debug-howto.rst for additional + information. + + Example usage: + + echo -n 'file "security/selinux/*" +p' > \ + /proc/dynamic_debug/control diff --git a/security/selinux/Makefile b/security/selinux/Makefile index 836379639058..c47519ed8156 100644 --- a/security/selinux/Makefile +++ b/security/selinux/Makefile @@ -12,6 +12,8 @@ obj-$(CONFIG_SECURITY_SELINUX) := selinux.o ccflags-y := -I$(srctree)/security/selinux -I$(srctree)/security/selinux/include +ccflags-$(CONFIG_SECURITY_SELINUX_DEBUG) += -DDEBUG + selinux-y := avc.o hooks.o selinuxfs.o netlink.o nlmsgtab.o netif.o \ netnode.o netport.o status.o \ ss/ebitmap.o ss/hashtab.o ss/symtab.o ss/sidtab.o ss/avtab.o \ From patchwork Fri Aug 18 15:12:15 2023 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: 13357930 X-Patchwork-Delegate: paul@paul-moore.com 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 E3E6AC7115A for ; Fri, 18 Aug 2023 15:13:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1377989AbjHRPND (ORCPT ); Fri, 18 Aug 2023 11:13:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34326 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1378079AbjHRPMq (ORCPT ); Fri, 18 Aug 2023 11:12:46 -0400 Received: from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com [IPv6:2a00:1450:4864:20::52d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0307F44BB; Fri, 18 Aug 2023 08:12:31 -0700 (PDT) Received: by mail-ed1-x52d.google.com with SMTP id 4fb4d7f45d1cf-5234f46c6f9so1302209a12.3; Fri, 18 Aug 2023 08:12:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692371549; x=1692976349; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=4/WNaebago/aJqZZVlC3lFxaEfE7d2mg3xgPUu5EqLQ=; b=Hcnq/di8BsbBcYaSke+l7b6FwHMPwVJFgYRLEAKgYIcEyDkBRT1VNXOhv0XFcX7mRZ RppUIGV9CXMCM6lk36f2jbfxdh5Vclnw+ON+qxvKUNu9ZihNI86AyHN5njcY3wgkjhA9 8RwvNNf4wqh5YOh5G6FejL6ml4dYgKSirRdBS8imftBECryhECYyoqUWK519IScauSNb KgYHAwieGkVPCPxQpJM/ycyJ2+EAKdPu/K4NR0mCPR05b2FRkA4mqH7fLeeuLhoN4S0L Zz9bxPT+1IZk2QRZtYb0Su0Ijipk7ZFDSSKrzq5nea4g0VRF8BY7we8WeymTEgNLYF0w mP9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692371549; x=1692976349; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=4/WNaebago/aJqZZVlC3lFxaEfE7d2mg3xgPUu5EqLQ=; b=kH1s5YHtVagSaSgPRE6UI47vEQKSv1lzhQ4iQz3YlO9On6kPPnEbMZ0VJ4FhogyLgC 04R+s+jsCzOaV/3Yqu/nr04hqloXQxpuhp3PY7/905CByKrRKOy727Eg6QECJrilyoyn USQbrKgWXKV6doZ8raOBMqql6LB5FivbWN+oz72mjHP+Jj/ZWZ532wdSmuqngOoSK0Ri uMFh1Wjv67xBetP47RVS9/kkz5QgErjS3bHRxSM+m54636HvNOu+pbTZHxCm/iJxm8er ts8ptS1WaVVsFPDhKxtHWCIPbUFOSUh/+6TB6FEeAjZTcTwyhkOX+s/U2wBHwuV3UF+S f8+Q== X-Gm-Message-State: AOJu0YxE3xJo5TuLXNEtGkBwdg5jCBoY0/8/Lq/dQ/IOdmZiVrb0x+3/ TXT0SCvO8yvBoZItgTah00NZH2Zdo/FQTQ== X-Google-Smtp-Source: AGHT+IGFWZElf1DbrvlGXU7UqtZRx9/EpHWXV8o2fqe4FEIPObb7LMccx5zwrREke6ZJS/lmKgcGqg== X-Received: by 2002:a17:906:d0:b0:965:6075:d100 with SMTP id 16-20020a17090600d000b009656075d100mr2203978eji.39.1692371549310; Fri, 18 Aug 2023 08:12:29 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-095-116-071-217.95.116.pool.telefonica.de. [95.116.71.217]) by smtp.gmail.com with ESMTPSA id sa19-20020a170906edb300b0099ca4f61a8bsm1285913ejb.92.2023.08.18.08.12.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Aug 2023 08:12:29 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: Paul Moore , Stephen Smalley , Eric Paris , Ondrej Mosnacek , linux-kernel@vger.kernel.org Subject: [PATCH 4/6] selinux: simplify avtab slot calculation Date: Fri, 18 Aug 2023 17:12:15 +0200 Message-Id: <20230818151220.166215-3-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230818151220.166215-1-cgzones@googlemail.com> References: <20230818151220.166215-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org Instead of dividing by 8 and then performing log2 by hand, use a more readable calculation. The behavior of rounddown_pow_of_two() for an input of 0 is undefined, so handle that case and small values manually to achieve the same results. Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley --- security/selinux/ss/avtab.c | 8 +------- 1 file changed, 1 insertion(+), 7 deletions(-) diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index 955cfe495606..1d1ffe085b35 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -298,13 +298,7 @@ int avtab_alloc(struct avtab *h, u32 nrules) u32 nslot = 0; if (nrules != 0) { - u32 shift = 1; - u32 work = nrules >> 3; - while (work) { - work >>= 1; - shift++; - } - nslot = 1 << shift; + nslot = nrules > 3 ? rounddown_pow_of_two(nrules / 2) : 2; if (nslot > MAX_AVTAB_HASH_BUCKETS) nslot = MAX_AVTAB_HASH_BUCKETS; From patchwork Fri Aug 18 15:12:16 2023 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: 13357934 X-Patchwork-Delegate: paul@paul-moore.com 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 0EED9C7EE2C for ; Fri, 18 Aug 2023 15:13:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1378035AbjHRPNF (ORCPT ); Fri, 18 Aug 2023 11:13:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59556 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1378087AbjHRPMr (ORCPT ); Fri, 18 Aug 2023 11:12:47 -0400 Received: from mail-ed1-x530.google.com (mail-ed1-x530.google.com [IPv6:2a00:1450:4864:20::530]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D37794684; Fri, 18 Aug 2023 08:12:32 -0700 (PDT) Received: by mail-ed1-x530.google.com with SMTP id 4fb4d7f45d1cf-52557cc5e7bso1290023a12.0; Fri, 18 Aug 2023 08:12:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692371551; x=1692976351; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=G1jVeMiv4f74U6MfEWdlEgNquQEP8X/dgMx+4n42j1I=; b=HTT6/COwSLC02B0rT+envRitn3bOH6mq3vpB6sl/GELyCq5Gh3Z45L7+3Qj3fAUGY7 CyFUJFP4LGfMsxEtQYiQIsbr40G2Ow7wOR/Uu5tyvVkLrT8WP1UT0Bouz14zC+htz/tj z9Wv39YPmeDTLTfTkK09IbPYbZJczy7H2POPGT18iIvzz3Ch64d5v+fYCTyg3tippHtP xx9vbGk14NeUZiPkZZ6wICoR7n1eOgsZu8XRfn3HkICUg+esfQdgx2mTy2nDSQ8OmIpR 0Q85V6xRvARZzJAo7/0YwOnqCF1fpGVpDG7rnyzayT/8dnzZDvwIoO3go4gYCo1Gve4U k6+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692371551; x=1692976351; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=G1jVeMiv4f74U6MfEWdlEgNquQEP8X/dgMx+4n42j1I=; b=J2GAEFuwGhbkFRijX5jeGdefVGOcSnr/ZqW7nZKnNUpgRClzZ2G32V5CYkwmR+3Wul 9HW7+kT97c4UOj0V7UUmdjo/W7M3mQVySrqD3itICFtcKTgRJk/27YQfthJvwj7uWIWk gsAXc1jeqnmCYhiiB2Tw6QE+7xwq7mOs1nKkb0KyquTdwxyDUrdBXx2CL+mgjx65cX57 kd7VVTqZGIuxqSljqhscqbfHyATq0YN0MNTKbKLyTfyEXNF1oEjwy/ZbbWwSUzfV3SHL PzzCAhuxLfRjnPizUATG9qvPBmwIgcWzYDRImKGNAUVVKtSNS1YgLebU/M923KQLecar 3nhA== X-Gm-Message-State: AOJu0YzWZNaqkouJFjucZU0aZ5947hBvpTmo+gmR5tlyZJHFgL9w2SOv 0HmzS2wl/jI+nrINcg7FycI7Pmgccckcaw== X-Google-Smtp-Source: AGHT+IGOgqKFUZ8bOuSHphStUiU1cg9eo/KR2DD/wMgeT/uF+UPvWhaQ/dR3qqBzYA31rQ0gOjtvqg== X-Received: by 2002:a17:906:5392:b0:992:42d4:a7dc with SMTP id g18-20020a170906539200b0099242d4a7dcmr2388918ejo.21.1692371551279; Fri, 18 Aug 2023 08:12:31 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-095-116-071-217.95.116.pool.telefonica.de. [95.116.71.217]) by smtp.gmail.com with ESMTPSA id sa19-20020a170906edb300b0099ca4f61a8bsm1285913ejb.92.2023.08.18.08.12.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Aug 2023 08:12:31 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: Paul Moore , Stephen Smalley , Eric Paris , Ondrej Mosnacek , linux-kernel@vger.kernel.org Subject: [PATCH 5/6] selinux: improve role transition hashing Date: Fri, 18 Aug 2023 17:12:16 +0200 Message-Id: <20230818151220.166215-4-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230818151220.166215-1-cgzones@googlemail.com> References: <20230818151220.166215-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The number of buckets is calculated by performing a binary AND against the mask of the hash table, which is one less than its size (which is a power of two). This leads to all top bits being discarded, e.g. with the Reference Policy on Debian there exists 376 entries, leading to a size of 512, discarding the top 23 bits. Use jhash to improve the hash table utilization: # current roletr: 376 entries and 124/512 buckets used, longest chain length 8, sum of chain length^2 1496 # patch roletr: 376 entries and 266/512 buckets used, longest chain length 4, sum of chain length^2 646 Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley --- security/selinux/ss/policydb.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 932e383bcad6..dd4a9eff61be 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -491,7 +491,7 @@ static u32 role_trans_hash(const void *k) { const struct role_trans_key *key = k; - return key->role + (key->type << 3) + (key->tclass << 5); + return jhash_3words(key->role, key->type, (u32)key->tclass << 16 | key->tclass, 0); } static int role_trans_cmp(const void *k1, const void *k2) From patchwork Fri Aug 18 15:12:17 2023 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: 13357932 X-Patchwork-Delegate: paul@paul-moore.com 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 A2354C7EE24 for ; Fri, 18 Aug 2023 15:13:37 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1378033AbjHRPNE (ORCPT ); Fri, 18 Aug 2023 11:13:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46922 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1378095AbjHRPMs (ORCPT ); Fri, 18 Aug 2023 11:12:48 -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 1D1AB4689; Fri, 18 Aug 2023 08:12:35 -0700 (PDT) Received: by mail-ej1-x62e.google.com with SMTP id a640c23a62f3a-99bdcade7fbso126168766b.1; Fri, 18 Aug 2023 08:12:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692371553; x=1692976353; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=zJbw1GCaNkp1mvMvks0R4KmZq/5vNngaaWzPgKdzcBI=; b=ksW2sAFDtA29aAzJUwQOx9s35kbGa38cSw6gn/6bghi/w/hDCnNOR6d/pJJgxsFJQV nvIYkxT8bY//ugPLl/NoVCre/uRgA5eCdjhQoQSHiu12/NDkdjwBfpUKHGoIFPOXJuLR 0ioWDR+toiAoESkX9Oxv0bYbzeomZBKccuBMZqudKFJkPfRWr/IwxWr59i4SFHDVVisn hN6cazsNtrLYTA4f8kBto5U5JkH2dLdj8AjdPLzGCpIQU7TDV1Ud0ATqRZ8JJ5tiTMXT FoCevzYhG8NajA9g0nsdkLA0nne+OINEbkYvZtv2XR6/HMvS7Ld24hF9GEWJVxuskGDv kSCA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692371553; x=1692976353; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=zJbw1GCaNkp1mvMvks0R4KmZq/5vNngaaWzPgKdzcBI=; b=C1pGWcmtnXFwdObk/YYv0h9Ld6MjrHehMZSzVNmVbMkrQChhVNNWY6Gx/qivTm5x9W 1EolcPP4utl7VyuMwLS7xYBfgjZVspo1/ig8MBhY+LEbgocAA/2d8wuQNWk1WoTRmFHx RsB3GmWasUx9ykvDMMY4aClxTvTTeehzp2TQA7zFnmniv18Jr3dTMltU7m6p/glrRMYr qcFGP1XiSEz5kGmJCVwZKKlBfMqYZSF7KaYtvrWLoC64a8kEJ8yQn8z/YZCkPa+ApyYm LjawS6BQJznR+hT2aRxA3Pn98WfWO+vUgRqZOO+jEJylIbvlqKT2h/nygnxhjxIVMwx2 pjGQ== X-Gm-Message-State: AOJu0YwidPqswAb6xVfDPLIihPch0joL7cbu1gpbb+D9y5iOFvg1MLZT QczQeO4dcfpX7dmTtbw9SdkAY30uih0g4w== X-Google-Smtp-Source: AGHT+IEA+txfXn8wU5i+Z9VkmOutImS3pUopFpT0HIgeXmvf7AQabi5uU9iMJS44FIOXvLcfFkKsHw== X-Received: by 2002:a17:907:762a:b0:988:9ec1:a8c5 with SMTP id jy10-20020a170907762a00b009889ec1a8c5mr1931135ejc.55.1692371553557; Fri, 18 Aug 2023 08:12:33 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-095-116-071-217.95.116.pool.telefonica.de. [95.116.71.217]) by smtp.gmail.com with ESMTPSA id sa19-20020a170906edb300b0099ca4f61a8bsm1285913ejb.92.2023.08.18.08.12.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 18 Aug 2023 08:12:33 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Cc: Paul Moore , Stephen Smalley , Eric Paris , Ondrej Mosnacek , linux-kernel@vger.kernel.org Subject: [PATCH 6/6] selinux: improve symtab string hashing Date: Fri, 18 Aug 2023 17:12:17 +0200 Message-Id: <20230818151220.166215-5-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230818151220.166215-1-cgzones@googlemail.com> References: <20230818151220.166215-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The number of buckets is calculated by performing a binary AND against the mask of the hash table, which is one less than its size (which is a power of two). This leads to all top bits being discarded, requiring for short or similar inputs a hash function with a good avalanche effect. Use djb2a: # current common prefixes: 7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11 classes: 134 entries and 100/256 buckets used, longest chain length 5, sum of chain length^2 234 roles: 15 entries and 6/16 buckets used, longest chain length 5, sum of chain length^2 57 types: 4448 entries and 3016/8192 buckets used, longest chain length 41, sum of chain length^2 14922 users: 7 entries and 3/8 buckets used, longest chain length 3, sum of chain length^2 17 bools: 306 entries and 221/512 buckets used, longest chain length 4, sum of chain length^2 524 levels: 1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1 categories: 1024 entries and 400/1024 buckets used, longest chain length 4, sum of chain length^2 2740 # patch common prefixes: 7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11 classes: 134 entries and 101/256 buckets used, longest chain length 3, sum of chain length^2 210 roles: 15 entries and 9/16 buckets used, longest chain length 3, sum of chain length^2 31 types: 4448 entries and 3459/8192 buckets used, longest chain length 5, sum of chain length^2 6778 users: 7 entries and 5/8 buckets used, longest chain length 3, sum of chain length^2 13 bools: 306 entries and 236/512 buckets used, longest chain length 5, sum of chain length^2 470 levels: 1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1 categories: 1024 entries and 518/1024 buckets used, longest chain length 7, sum of chain length^2 2992 Signed-off-by: Christian Göttsche Reviewed-by: Stephen Smalley --- security/selinux/ss/symtab.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-) diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c index 43d7f0319ccd..b6761b96eee4 100644 --- a/security/selinux/ss/symtab.c +++ b/security/selinux/ss/symtab.c @@ -11,16 +11,14 @@ static unsigned int symhash(const void *key) { - const char *p, *keyp; - unsigned int size; - unsigned int val; - - val = 0; - keyp = key; - size = strlen(keyp); - for (p = keyp; (p - keyp) < size; p++) - val = (val << 4 | (val >> (8*sizeof(unsigned int)-4))) ^ (*p); - return val; + /* djb2a */ + unsigned int hash = 5381; + unsigned char c; + + while ((c = *(const unsigned char *)key++)) + hash = ((hash << 5) + hash) ^ c; + + return hash; } static int symcmp(const void *key1, const void *key2)