From patchwork Wed Aug 16 12:38:41 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: 13355151 X-Patchwork-Delegate: plautrba@redhat.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 CE677C001B0 for ; Wed, 16 Aug 2023 12:39:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S244571AbjHPMjN (ORCPT ); Wed, 16 Aug 2023 08:39:13 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35092 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245334AbjHPMjB (ORCPT ); Wed, 16 Aug 2023 08:39:01 -0400 Received: from mail-ej1-x629.google.com (mail-ej1-x629.google.com [IPv6:2a00:1450:4864:20::629]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 62A5E1FF9 for ; Wed, 16 Aug 2023 05:39:00 -0700 (PDT) Received: by mail-ej1-x629.google.com with SMTP id a640c23a62f3a-99bccc9ec02so906283866b.2 for ; Wed, 16 Aug 2023 05:39:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692189539; x=1692794339; h=content-transfer-encoding:mime-version:message-id:date:subject:to :from:from:to:cc:subject:date:message-id:reply-to; bh=/+eEK6P0Emorw5bqNn4hrxlxmAnnitBogOhVrqsDH/0=; b=gZb+rEx384h0w+LO4arkODmSgek3G+SYKm/uYi13hflKlZU1tu43gGRDpDB08py0ba MG4dqMx5yEbBnnhCniEysDJwoqiMCvGZAIRU6a4gZvwPuqrILm9azN8keXte62hxxlwr R1aX/NvAN9XymTxvaCMaIDv0VaG2SqCNdNofXimup2UD3LnxvmQwwRRMdchdDZa9d3vZ cu856g81B4eh60ZfPXc/m3XH3djyaa0ZiBNCNl9sxNk19cJXeOqNKkceUHgGiK1RAc8L VRygLYNiswZ4e297zcNX+RdXAArTFXHhazOQ+qFgyIJlu6/HsjmWmYAxjR5ZVm4jz2o7 shhw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692189539; x=1692794339; h=content-transfer-encoding:mime-version:message-id:date:subject:to :from:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=/+eEK6P0Emorw5bqNn4hrxlxmAnnitBogOhVrqsDH/0=; b=NziHudhV3glfqWBVN5Pteqp0X9eKXFb1JgU7MAb3FWCs+JJixrgxka4O2woa7M+XcF 7l8l57Mlo4PQ5XERFcLM0oAtwCrJvHm5tk+sxqAaJcjWUneNqNKAXjyjjqFl4OupSTLL bHIyRpXnfFszfOBonrEU6Eou/KD5RouhQGoDr/+VzaH3lDSJIgm6Mr9hdmWNfMNo0Giu nkCmcmxc25lKTgXdHd663V5hZo+mUN73i2nT+I/XQA7GW2Zy8XeiL0mXUOnwL2MQnx5Q rBrIbbGfjQPkwR7ONR92yo/21Udy5YDEupFjhNnyz0Kz2mTe05ZX8XEEkcwivcBTUk9G ZmCQ== X-Gm-Message-State: AOJu0YwRsTLMI/q1M6ePlCUrSz85s+o4KGZmmeIapQubGWTMeU/USMI0 PVhgvvGL70m0cE1rQ7tf58TUY4LVKKQLtGSn X-Google-Smtp-Source: AGHT+IESHjQVDC6Prx/A/1FOClkhgAgWc2VmUEg17/5OSIFzQDTacoeJ7rh3SJ1qaZ3olXCIeyzLTA== X-Received: by 2002:a17:906:cc18:b0:99c:bb4d:f5a1 with SMTP id ml24-20020a170906cc1800b0099cbb4df5a1mr1195412ejb.4.1692189538666; Wed, 16 Aug 2023 05:38:58 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-077-001-094-128.77.1.pool.telefonica.de. [77.1.94.128]) by smtp.gmail.com with ESMTPSA id l27-20020a170906415b00b009886aaeb722sm8434075ejk.137.2023.08.16.05.38.58 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 16 Aug 2023 05:38:58 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 1/5] libsepol: include length squared in hashtab_hash_eval() Date: Wed, 16 Aug 2023 14:38:41 +0200 Message-Id: <20230816123845.80171-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 Include the chain length squared sum as metric in the debug function hashtab_hash_eval(), adopted from the kernel avtab. Signed-off-by: Christian Göttsche --- libsepol/src/hashtab.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-) diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c index b1a9bdc2..2af3a9bf 100644 --- a/libsepol/src/hashtab.c +++ b/libsepol/src/hashtab.c @@ -243,11 +243,12 @@ int hashtab_map(hashtab_t h, void hashtab_hash_eval(hashtab_t h, const char *tag) { unsigned int i; - size_t chain_len, slots_used, max_chain_len; + size_t chain_len, slots_used, max_chain_len, chain2_len_sum; hashtab_ptr_t 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) { @@ -260,10 +261,12 @@ void hashtab_hash_eval(hashtab_t h, const char *tag) if (chain_len > max_chain_len) max_chain_len = chain_len; + chain2_len_sum += chain_len * chain_len; } } printf - ("%s: %d entries and %zu/%d buckets used, longest chain length %zu\n", - tag, h->nel, slots_used, h->size, max_chain_len); + ("%s: %d entries and %zu/%d buckets used, longest chain length %zu, chain length^2 %zu, normalized chain length^2 %.2f\n", + tag, h->nel, slots_used, h->size, max_chain_len, chain2_len_sum, + chain2_len_sum ? (float)chain2_len_sum / slots_used : 0); } From patchwork Wed Aug 16 12:38:42 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: 13355155 X-Patchwork-Delegate: plautrba@redhat.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 23229C04E69 for ; Wed, 16 Aug 2023 12:39:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S244675AbjHPMjN (ORCPT ); Wed, 16 Aug 2023 08:39:13 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35120 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245339AbjHPMjD (ORCPT ); Wed, 16 Aug 2023 08:39:03 -0400 Received: from mail-ed1-x535.google.com (mail-ed1-x535.google.com [IPv6:2a00:1450:4864:20::535]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CA7A4211E for ; Wed, 16 Aug 2023 05:39:00 -0700 (PDT) Received: by mail-ed1-x535.google.com with SMTP id 4fb4d7f45d1cf-525597d891fso4885081a12.3 for ; Wed, 16 Aug 2023 05:39:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692189539; x=1692794339; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=TqIGz5TKkb4E1kbvULKruf/3JJhLy36IztWTYKBbei8=; b=eetLqIwYD5uFrf4kmr08yEJ2UWQMQmiLfeptoWcvmBQPg5QL9r+voiS4ncbaY+7sVI IX8yfF1UWJpebfHXV21D/jNXYgWPH0S5x+GjS+Y+z7ew/ZsBeIR0P7yUqeZ922ZZJ8Jy Iggue4HkMOybo9FTZyGN2iKFYtlYykPcq6bVtgbeFhq5oBPiJ9fWQ3eN6eW3hBR2sccl X7Is61wZelENaM4C08wMt7owK5BGmijL6luR36s8ObotxvN/qVx7326NtClgq/VPpKb1 I20gcAsi3CsL2iUlhMrsnSA67bpLKeEDRBatv57epTQ8PXR1A85Onhqm5kb+jDG/nT2I AXrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692189539; x=1692794339; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=TqIGz5TKkb4E1kbvULKruf/3JJhLy36IztWTYKBbei8=; b=goEqF4DmGnvEPbnMnHmB8qPmvB8yrV19PxE/RR0hjUKC/ll/KLk+igl2zUS2c5mC2I gAEFyS61VL88WjcmWHO2F/CzgJgN57HyPfXxzFIkBOVWWYOp8hFU0SZR0g/q4g92u5Wz L+IVE0fQ/zl47bgYzXHihlLjr48yISJT67c7lrqbYl+giortft5bRzU0vMbQg+O7PXoa MCCxKf3jp67qvEfXz147e+fsrrpfVHO5jGL9IfyjFda2uQRzc9r6H5PNYnvU+tDN9t/h zV1g/4fMuthqK1KGyYlrrEb9lv+1N4tPC++U1rQB9OdeT3Qh1XzidUFRL+7pSNqLHuv2 7YcA== X-Gm-Message-State: AOJu0YxFIdLBf8mqjRbNfCvn/Gqa4rQt0l7vHzxW496OA97KuuUd7AEZ 6QdDe7hJryGUzay+xi+YLJE3Yn3slehcNfxo X-Google-Smtp-Source: AGHT+IEXIvQ6ZNfHgY+mbvjJIuh3bLU2j56kvqtfcx400PxSJCWDDrwm3AQcFfLm2Xpl3NscWqurfg== X-Received: by 2002:a17:906:cc0d:b0:99d:7336:728c with SMTP id ml13-20020a170906cc0d00b0099d7336728cmr1247968ejb.35.1692189539231; Wed, 16 Aug 2023 05:38:59 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-077-001-094-128.77.1.pool.telefonica.de. [77.1.94.128]) by smtp.gmail.com with ESMTPSA id l27-20020a170906415b00b009886aaeb722sm8434075ejk.137.2023.08.16.05.38.58 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 16 Aug 2023 05:38:58 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 2/5] libsepol: use DJB2a string hash function Date: Wed, 16 Aug 2023 14:38:42 +0200 Message-Id: <20230816123845.80171-2-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230816123845.80171-1-cgzones@googlemail.com> References: <20230816123845.80171-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The hash table implementation uses `& (h->size - 1)` to truncate generated hashes to the number of buckets. This operation is equal to `% h->size` if and only if the size is a power of two (which seems to be always the case). One property of the binary and with a power of two (and probably a small one <=2048) is all higher bits are discarded. Thus a hash function is needed with a good avalanche effect, which the current one is not. Benchmark of building Reference Policy: # Current Benchmark 1: /tmp/destdir/usr/bin/checkpolicy -c 33 -U deny -S -O -E policy.conf -o policy.33 Time (mean ± σ): 2.521 s ± 0.025 s [User: 2.442 s, System: 0.076 s] Range (min … max): 2.467 s … 2.550 s 10 runs # Patch Benchmark 1: /tmp/destdir/usr/bin/checkpolicy -c 33 -U deny -S -O -E policy.conf -o policy.33 Time (mean ± σ): 2.385 s ± 0.031 s [User: 2.303 s, System: 0.081 s] Range (min … max): 2.353 s … 2.446 s 10 runs Signed-off-by: Christian Göttsche --- libsepol/src/symtab.c | 18 +++++++----------- 1 file changed, 7 insertions(+), 11 deletions(-) diff --git a/libsepol/src/symtab.c b/libsepol/src/symtab.c index 78567dbf..4b45c549 100644 --- a/libsepol/src/symtab.c +++ b/libsepol/src/symtab.c @@ -17,17 +17,13 @@ ignore_unsigned_overflow_ static unsigned int symhash(hashtab_t h, const_hashtab_key_t key) { - const char *p, *keyp; - size_t size; - unsigned int val; - - val = 0; - keyp = (const char *)key; - size = strlen(keyp); - for (p = keyp; ((size_t) (p - keyp)) < size; p++) - val = - (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p); - return val & (h->size - 1); + unsigned int hash = 5381; + unsigned char c; + + while ((c = *(unsigned const char *)key++)) + hash = ((hash << 5) + hash) ^ c; + + return hash & (h->size - 1); } static int symcmp(hashtab_t h From patchwork Wed Aug 16 12:38:43 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: 13355153 X-Patchwork-Delegate: plautrba@redhat.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 1117FC41513 for ; Wed, 16 Aug 2023 12:39:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S244516AbjHPMjO (ORCPT ); Wed, 16 Aug 2023 08:39:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35098 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245336AbjHPMjC (ORCPT ); Wed, 16 Aug 2023 08:39:02 -0400 Received: from mail-ej1-x629.google.com (mail-ej1-x629.google.com [IPv6:2a00:1450:4864:20::629]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4BC9326B1 for ; Wed, 16 Aug 2023 05:39:01 -0700 (PDT) Received: by mail-ej1-x629.google.com with SMTP id a640c23a62f3a-99d90ffed68so857205166b.0 for ; Wed, 16 Aug 2023 05:39:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692189540; x=1692794340; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=Sg6l6Rhu1p5H5AHYMUEAumZ4eKjnIcBrWpBZ+y3B+wQ=; b=qM6/FgIW8Ig61/yIr9Xg8W5tynjtFCBwvPr6jLEVvGzgoD65R4ghS84HrqRRlNOi6a FWkvdkJogL8Hm9uiPXwhRaflxfKipiXoXLMowLdWlnI+oZVubxegXUU+MUSfDVTfLHhZ OXLU7xEYqg/hJ/Zl02ibVrccZBzr+OtoY4dH1Cez/ldRU/OXwcg7aRrJMCooORIe+Y2L yxLjDry4qVBfNepH7aM+T0NGYnAXpaqf7jVzpsa3O7MuhsRRKzcnEJdTwMQPuvJoQ2zV JeTv/2SYUaS0q92at9q83YuEzymshEsK9vWFxvsqkkmv8M56cH3/ESb00bcJuYhW+hYJ oU7Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692189540; x=1692794340; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Sg6l6Rhu1p5H5AHYMUEAumZ4eKjnIcBrWpBZ+y3B+wQ=; b=LlFUqp/XqM1zfDCBUOBXyzvli8mItjrkC9M811rubmIUGNDuwZt4rGjduLR+o8ku6g 1fF7LlCOfPN6L9KJCCKdPV++QxM7BnfeOLmjZasw6aZM18IZRn2Ejd3yo9XYmC3GkmP7 lbVC/iYZB5wJbGfe+DLfAfN7Huk0O4pdSGFqlZyCaEPWyl4OY5tJq4FJT/tJFU2kYgPJ EdOyDCzVLl3AtY0ffyesFER5gz4oOCan7Y5PewzfF4emU9lQUjwnvm/6DSL1tIagSigw e59WIUk6pscvek+YxO5/vK/J92YqM1aqByRfxM+BbAv4bpGFoOOiyeryl8uI2hbHMzuj AP4g== X-Gm-Message-State: AOJu0YxazmKX7zRcaPshEK7wH9RVgvsvEaEZwhiD1BHc5Ae5TSNdvF+p h0it+rst5mo8ofPPoncpMQ3i2cThjDFgdMi7 X-Google-Smtp-Source: AGHT+IEAJFjD8AiI44+LLh8r7dOOjttlnLqzg58a37RUzTMsBc83xOn3lnLvEFqtwbnLMRQz4lqClg== X-Received: by 2002:a17:906:519e:b0:99d:decd:3deb with SMTP id y30-20020a170906519e00b0099ddecd3debmr2532114ejk.14.1692189539760; Wed, 16 Aug 2023 05:38:59 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-077-001-094-128.77.1.pool.telefonica.de. [77.1.94.128]) by smtp.gmail.com with ESMTPSA id l27-20020a170906415b00b009886aaeb722sm8434075ejk.137.2023.08.16.05.38.59 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 16 Aug 2023 05:38:59 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 3/5] libsepol/cil: use DJB2a string hash function Date: Wed, 16 Aug 2023 14:38:43 +0200 Message-Id: <20230816123845.80171-3-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230816123845.80171-1-cgzones@googlemail.com> References: <20230816123845.80171-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The hash table implementation uses `& (h->size - 1)` to truncate generated hashes to the number of buckets. This operation is equal to `% h->size` if and only if the size is a power of two (which seems to be always the case). One property of the binary and with a power of two (and probably a small one <=2048) is all higher bits are discarded. Thus a hash function is needed with a good avalanche effect, which the current one is not. Benchmark of building dssp5: # Current Time (mean ± σ): 1.347 s ± 0.065 s [User: 1.207 s, System: 0.138 s] Range (min … max): 1.274 s … 1.436 s 10 runs # Patch Time (mean ± σ): 1.336 s ± 0.029 s [User: 1.195 s, System: 0.140 s] Range (min … max): 1.303 s … 1.376 s 10 runs Signed-off-by: Christian Göttsche --- libsepol/cil/src/cil_strpool.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) diff --git a/libsepol/cil/src/cil_strpool.c b/libsepol/cil/src/cil_strpool.c index e32ee4e9..beea5c9d 100644 --- a/libsepol/cil/src/cil_strpool.c +++ b/libsepol/cil/src/cil_strpool.c @@ -47,16 +47,13 @@ static hashtab_t cil_strpool_tab = NULL; static unsigned int cil_strpool_hash(hashtab_t h, const_hashtab_key_t key) { - const char *p; - size_t size; - unsigned int val; + unsigned int hash = 5381; + unsigned char c; - val = 0; - size = strlen(key); - for (p = key; ((size_t) (p - key)) < size; p++) - val = - (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p); - return val & (h->size - 1); + while ((c = *(unsigned const char *)key++)) + hash = ((hash << 5) + hash) ^ c; + + return hash & (h->size - 1); } static int cil_strpool_compare(hashtab_t h __attribute__ ((unused)), const_hashtab_key_t key1, const_hashtab_key_t key2) From patchwork Wed Aug 16 12:38:44 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: 13355152 X-Patchwork-Delegate: plautrba@redhat.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 EEBBDC001B0 for ; Wed, 16 Aug 2023 12:39:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S244924AbjHPMjO (ORCPT ); Wed, 16 Aug 2023 08:39:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35104 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245337AbjHPMjD (ORCPT ); Wed, 16 Aug 2023 08:39:03 -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 E40291FF9 for ; Wed, 16 Aug 2023 05:39:01 -0700 (PDT) Received: by mail-ej1-x634.google.com with SMTP id a640c23a62f3a-99c93638322so1341188066b.1 for ; Wed, 16 Aug 2023 05:39:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692189540; x=1692794340; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=zV8Nj7OSIjTcqPOry4WQD9ptaRYnPm3zWW0w3f0QsoU=; b=gx99UklzAc9ZyYY758iJwiH2C7+ngOGjDPfkIGlUXMi7soIMj+t1/YjG5iQ21XOgB+ 3vTcYKa3dPsuibDdXhfFmqvFw+AEGXpJ5l6fqdEaBQilnmPEKYiAvB08yUYwkdx7zgqd eW1WCjb/sQ9qv6KGR9Sb5j/2DO/dS1OQfzHQ+7UyCPYMkgzsoT8wVgibi1GTipMXLLMR 6kQ9M9XlagED9lT1xUvqSfHe7vQL5fAO8NsDMujCErmvUhDSkBWA9MBMHQxH5htSvJzT siFXU00/8VI8dcNDTCwYDOs4arvoAkpruxIP5Dqre+BZDLO/gDph3ZqqflhL7WOGa9zy Fc8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692189540; x=1692794340; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=zV8Nj7OSIjTcqPOry4WQD9ptaRYnPm3zWW0w3f0QsoU=; b=Ituel3iTfzOmdWufOHyZzzm3YE6EJYlU9wQFy+3RMIFe4vfQeTzC3MRA3eo2pR+y0b A2m/VJZ52BV54ngvc3X/V58w53KSE+cAsPRLw2eSijDUGDBbGfD1jYWI9LtQKFPgmd7l RLTglnWPZiXaRxAUDSRwyLgvYSRGo8jeKzFef13ToOpnJ5eG8LT7n3VA0tT9ae5dbBV5 vRJCWsdJCPGpuGtAco8Bg0MGnp1QgmH4aF4vpYkn4CFvwfkUoyGuubBUUofOZH8wb7I2 ZAJj8cRo1PJf0uULTKpk7ltrhetSEvOSD67LrgsxwShcdKReFCKlQ423QftzWNZqSbzl jryw== X-Gm-Message-State: AOJu0YwtarmAD5CohLGwJ6zNcLOjFy1kOH7z5lELNee/PvhFLfZxuGHl q26Cy8/XytVOSP2LYNj/G1z6B9t520R6ATwb X-Google-Smtp-Source: AGHT+IFf71fVW5Q1zN98d5qFabGHYfj/Ygs1RejWhv6F6/NCtqzF66G4h1sh4GcSdThsyP8BE1bjDA== X-Received: by 2002:a17:906:5a46:b0:997:e7d0:e26d with SMTP id my6-20020a1709065a4600b00997e7d0e26dmr2140499ejc.4.1692189540242; Wed, 16 Aug 2023 05:39:00 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-077-001-094-128.77.1.pool.telefonica.de. [77.1.94.128]) by smtp.gmail.com with ESMTPSA id l27-20020a170906415b00b009886aaeb722sm8434075ejk.137.2023.08.16.05.38.59 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 16 Aug 2023 05:38:59 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 4/5] libselinux: use DJB2a string hash function Date: Wed, 16 Aug 2023 14:38:44 +0200 Message-Id: <20230816123845.80171-4-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230816123845.80171-1-cgzones@googlemail.com> References: <20230816123845.80171-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The hash table implementation uses `& (SIDTAB_SIZE - 1)` to truncate generated hashes to the number of buckets. This operation is equal to `% SIDTAB_SIZE` if and only if the size is a power of two (which seems to be always the case). One property of the binary and with a power of two (and probably a small one <=2048) is all higher bits are discarded. Thus a hash function is needed with a good avalanche effect, which the current one is not. Signed-off-by: Christian Göttsche --- libselinux/src/avc_sidtab.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/libselinux/src/avc_sidtab.c b/libselinux/src/avc_sidtab.c index f179d855..e396a938 100644 --- a/libselinux/src/avc_sidtab.c +++ b/libselinux/src/avc_sidtab.c @@ -15,16 +15,13 @@ static inline unsigned sidtab_hash(const char * key) { - const char *p; - unsigned int size; - unsigned int val; - - val = 0; - size = strlen(key); - for (p = key; (unsigned int)(p - key) < size; p++) - val = - (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p); - return val & (SIDTAB_SIZE - 1); + unsigned int hash = 5381; + unsigned char c; + + while ((c = *(unsigned const char *)key++)) + hash = ((hash << 5) + hash) ^ c; + + return hash & (SIDTAB_SIZE - 1); } int sidtab_init(struct sidtab *s) From patchwork Wed Aug 16 12:38:45 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: 13355154 X-Patchwork-Delegate: plautrba@redhat.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 337A6C04FDF for ; Wed, 16 Aug 2023 12:39:45 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S245283AbjHPMjO (ORCPT ); Wed, 16 Aug 2023 08:39:14 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35136 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S245341AbjHPMjE (ORCPT ); Wed, 16 Aug 2023 08:39:04 -0400 Received: from mail-ej1-x62f.google.com (mail-ej1-x62f.google.com [IPv6:2a00:1450:4864:20::62f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6685E26AD for ; Wed, 16 Aug 2023 05:39:02 -0700 (PDT) Received: by mail-ej1-x62f.google.com with SMTP id a640c23a62f3a-99c4923195dso878622366b.2 for ; Wed, 16 Aug 2023 05:39:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20221208; t=1692189541; x=1692794341; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=xRKI2CkRVXkPU8ujHaTJKF3+4wx1OlgSghxDrBnixgA=; b=L2lS569m9knaVmLxglzcTUdnSVlncl9RmWQUCK9HWbXchD/OM1h1ktRr9qWDoq+YuC hpS3IWzjhcVmjRApK5sQMWxJY94zRmiJVOmYRS7cnCihYJlgvZBcnWB1dGc7kWKagQX+ qh7R1ftajv8WeV1ZoFNFRFOOdbHeyJMwN+uXce6LPB4tmydNvVI8Idigo6jNSFCiAuRx daxKmiu/B9DA6Od5E9zAcf9qFeXJnuDfo9Fvywo1u1VPeFVEOPRYWzM/+/QjoG0rfHvg xWufCBuNw5WTbwTu14ke5bhfSBc7xu/+453Tg0L5nyroOrZ/41X7pLfULyJK1nwyG8GH Debw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1692189541; x=1692794341; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=xRKI2CkRVXkPU8ujHaTJKF3+4wx1OlgSghxDrBnixgA=; b=GDcblcz5XEo5URW4FI0QrIIq4jixmQK31akyx/S2fO3itqjdOpo4L8kq/tjmVmcM9p 0xG0XoNJq7UwN6iNwVM9uYPkLVSv63fEzyWnHbG5HDowpG5cnspJFu17eYqH48l0MsjX /gyALCxPrVo29YCerYKolJSPYldFae6rFW9whm+cq8/CeDihmK2P12nfqngfUhxBeKNJ 3MkD452JntOGN3zycrdVXH0k6M8nKJ0CdeKqp27uSbCu0m6/3YR71APmPWTIAboR7ntY O9D2CaVKh8v1MrS3JaKkg3xcsb3etOpcZD5dAEMUo1S0JKLpWoSeC1UbWMVMyFkgs8bO DG1Q== X-Gm-Message-State: AOJu0YzCgZeCvuozDBEl7ursqP9I4evqzeYKWFMNHSKZ0dZE6P5hxxrh 6gAlr7cQ3FKhIAs2K/oqbMM5U0Q062waQ2ZC X-Google-Smtp-Source: AGHT+IHFQX6PLwKaFUaZhVjYMAXgLBBOGJGTL+u/f0TIFTWuxDi3l8LDkc5mxtFjUYpt1X++Esu5Cg== X-Received: by 2002:a17:907:784b:b0:99b:dd1d:bc58 with SMTP id lb11-20020a170907784b00b0099bdd1dbc58mr1335170ejc.41.1692189540762; Wed, 16 Aug 2023 05:39:00 -0700 (PDT) Received: from debian_development.DebianHome (dynamic-077-001-094-128.77.1.pool.telefonica.de. [77.1.94.128]) by smtp.gmail.com with ESMTPSA id l27-20020a170906415b00b009886aaeb722sm8434075ejk.137.2023.08.16.05.39.00 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 16 Aug 2023 05:39:00 -0700 (PDT) From: =?utf-8?q?Christian_G=C3=B6ttsche?= To: selinux@vger.kernel.org Subject: [PATCH 5/5] newrole: use DJB2a string hash function Date: Wed, 16 Aug 2023 14:38:45 +0200 Message-Id: <20230816123845.80171-5-cgzones@googlemail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230816123845.80171-1-cgzones@googlemail.com> References: <20230816123845.80171-1-cgzones@googlemail.com> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: selinux@vger.kernel.org The hash table implementation uses `& (h->size - 1)` to truncate generated hashes to the number of buckets. This operation is equal to `% h->size` if and only if the size is a power of two (which seems to be always the case). One property of the binary and with a power of two (and probably a small one <=2048) is all higher bits are discarded. Thus a hash function is needed with a good avalanche effect, which the current one is not. Signed-off-by: Christian Göttsche --- policycoreutils/newrole/newrole.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) diff --git a/policycoreutils/newrole/newrole.c b/policycoreutils/newrole/newrole.c index d9efa68a..5a1a1129 100644 --- a/policycoreutils/newrole/newrole.c +++ b/policycoreutils/newrole/newrole.c @@ -229,16 +229,13 @@ static int free_hashtab_entry(hashtab_key_t key, hashtab_datum_t d, static unsigned int reqsymhash(hashtab_t h, const_hashtab_key_t key) { - const char *p; - size_t size; - unsigned int val; - - val = 0; - size = strlen(key); - for (p = key; ((size_t) (p - key)) < size; p++) - val = - (val << 4 | (val >> (8 * sizeof(unsigned int) - 4))) ^ (*p); - return val & (h->size - 1); + unsigned int hash = 5381; + unsigned char c; + + while ((c = *(unsigned const char *)key++)) + hash = ((hash << 5) + hash) ^ c; + + return hash & (h->size - 1); } static int reqsymcmp(hashtab_t h