From patchwork Mon Apr 25 15:58:09 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53192 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 522C03858C74 for ; Mon, 25 Apr 2022 15:58:43 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 522C03858C74 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902323; bh=J4sEQHrShPaKJuxTrePMdayFSggo+GVOrwcVSe3S4uw=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=JZuKHBRER0yKQ8JqNWYnUS1XgYyAC+QXWmSDVLjoMt7IpDbRFOktYB+ySzwMiP4Tq nBLn0LJ22LOjT64Itf+YO2cjzU8YeqFB9MYXF3Ot5eMq+EK4KpxoACIQ8p8SuFfOEx FaopYyYaWN+AHWgZylfnzkN28hf235Xth4qeOb+8= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd29.google.com (mail-io1-xd29.google.com [IPv6:2607:f8b0:4864:20::d29]) by sourceware.org (Postfix) with ESMTPS id 8A63F3858D28 for ; Mon, 25 Apr 2022 15:58:20 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8A63F3858D28 Received: by mail-io1-xd29.google.com with SMTP id n134so16303668iod.5 for ; Mon, 25 Apr 2022 08:58:20 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=J4sEQHrShPaKJuxTrePMdayFSggo+GVOrwcVSe3S4uw=; b=Uge4mMwcfsluk3kU3Jq0iYCJc1YjFWw25gC52u5MMb926UHnScz7cg7s5TvyXzI8bT 3kFlryS/YCq1eHAXAAd17NKXj5faKpQVPg+P1r0fuauheDwQHHVpauc+KhEvlkoLwKFQ jCw2xqPlwoBr54d4A/lKHLGbx5xGl/bGLhNjD4Qj4V1f2P2H2f/MTv5I1H5fzdnrcBH2 HdjPTx+elZKjIRIq4sZNTB31T2sDce4xlbdR7Lpp8oz62w6MdXZ2yjLt7h19Kfzf+dgu BlmqKVY3QmAtQlM3c/0YeGzMX1GNgQe5okjtGeCoIrLmnmRwZLMTMQc8+DX7b4keQYWl 1WNQ== X-Gm-Message-State: AOAM530ve56Oh7AEc63FoC6+17MhLCA25kY3NBAKdKsV0AUx8WOaz1ei L+L4+wwZ0vJmNjCWDl0qjNxkZum7GZc= X-Google-Smtp-Source: ABdhPJyolKsMBMsKpn35xVi5vMuOSmwcL5NseNeV21WZUMny1RZr+xcvpwLetDUrsXb3YeI9lgtbxA== X-Received: by 2002:a05:6602:14c4:b0:657:2e9c:735e with SMTP id b4-20020a05660214c400b006572e9c735emr7418308iow.159.1650902299643; Mon, 25 Apr 2022 08:58:19 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:19 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked Date: Mon, 25 Apr 2022 10:58:09 -0500 Message-Id: <20220425155814.3558359-1-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414041231.926415-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" No change to the code other than moving the function to dl-new-hash.h. Changed name so its now in the reserved namespace. --- elf/dl-lookup.c | 13 ++----------- elf/dl-new-hash.h | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+), 11 deletions(-) create mode 100644 elf/dl-new-hash.h diff --git a/elf/dl-lookup.c b/elf/dl-lookup.c index 989b073e4f..a42f6d5390 100644 --- a/elf/dl-lookup.c +++ b/elf/dl-lookup.c @@ -24,6 +24,7 @@ #include #include #include +#include #include #include #include @@ -558,16 +559,6 @@ skip: } -static uint32_t -dl_new_hash (const char *s) -{ - uint32_t h = 5381; - for (unsigned char c = *s; c != '\0'; c = *++s) - h = h * 33 + c; - return h; -} - - /* Add extra dependency on MAP to UNDEF_MAP. */ static int add_dependency (struct link_map *undef_map, struct link_map *map, int flags) @@ -816,7 +807,7 @@ _dl_lookup_symbol_x (const char *undef_name, struct link_map *undef_map, const struct r_found_version *version, int type_class, int flags, struct link_map *skip_map) { - const unsigned int new_hash = dl_new_hash (undef_name); + const unsigned int new_hash = _dl_new_hash (undef_name); unsigned long int old_hash = 0xffffffff; struct sym_val current_value = { NULL, NULL }; struct r_scope_elem **scope = symbol_scope; diff --git a/elf/dl-new-hash.h b/elf/dl-new-hash.h new file mode 100644 index 0000000000..52eef4e417 --- /dev/null +++ b/elf/dl-new-hash.h @@ -0,0 +1,34 @@ +/* _dl_new_hash for elf symbol lookup + Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#ifndef _DL_NEW_HASH_H +#define _DL_NEW_HASH_H 1 + +#include + +static uint32_t +_dl_new_hash (const char *s) +{ + uint32_t h = 5381; + for (unsigned char c = *s; c != '\0'; c = *++s) + h = h * 33 + c; + return h; +} + + +#endif /* dl-new-hash.h */ From patchwork Mon Apr 25 15:58:10 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53193 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 25AD6385840C for ; Mon, 25 Apr 2022 15:59:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 25AD6385840C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902365; bh=3Pvgt2ZLk5m/tmc9J2reTrbqFmOteW/H0XHoLQFsm9I=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=ab5f5NDExlk1pM44P/Fbt11zEiMRHqpKkaGcz329SrcwpyMLneu/Uxw+k69Ys331H lb9LJ3Wj0o4Y7SYfaMKvhREUQcWdxxbDbFM1dN8LsPzY4QjhAV9JUCJQJM4sSHH6CW htwPdp8j5nVmfIQpAdr/HfWESVtSyWazKj5WOAsY= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x131.google.com (mail-il1-x131.google.com [IPv6:2607:f8b0:4864:20::131]) by sourceware.org (Postfix) with ESMTPS id 95A753858C83 for ; Mon, 25 Apr 2022 15:58:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 95A753858C83 Received: by mail-il1-x131.google.com with SMTP id y11so9629040ilp.4 for ; Mon, 25 Apr 2022 08:58:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=3Pvgt2ZLk5m/tmc9J2reTrbqFmOteW/H0XHoLQFsm9I=; b=3cjRLtqpPeSGn5Sd66m2mbvbMvC+z37txGOWmW4JFvheKVs3q9hJi+SjFEvFZvbIEV mnwDZuiDGhHbAZvi/RdsEkFiXB7fwvUW0dyT9kxQsPvon+a2k9Mb8EdYNahgqwdHrml7 LMfQh0Er+Sg294tBqcIFj/OKVhbnD1v25NgneF2fAokoLGWK+PN1/1Mi8ma+F5DB4TbE Jl5ZbfJ3po9an2HIxbfHXBHNqDtv4dZfyl6cPa9z1HJsDQDCl/w1+igxqVODbEy88oQI CKCY3FqtneKTFk8DZ89XTQ6cvhlEyQtrIBJcFOIW4lxB/puVAJ3+SP3dAVS5dfCMaQLw tU/w== X-Gm-Message-State: AOAM530FEhmsN2+2UZmm9aylwsLvC7JMp4BhTzOhRlafXZiPJDBN6jLX HNfxJcx6Tj3Wyws88oQeE9m34NoHC78= X-Google-Smtp-Source: ABdhPJwslrQp/NF/l5Jh5JAZiiqR4/yHvmjAUg9aDGAkVS35ERmcqZGd+lCc5TFFlpJfhBtU/CFLhg== X-Received: by 2002:a05:6e02:1c0e:b0:2cc:37f3:6221 with SMTP id l14-20020a056e021c0e00b002cc37f36221mr7765795ilh.136.1650902300704; Mon, 25 Apr 2022 08:58:20 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:20 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 2/6] elf: Add tests for the dl hash funcs (_dl_new_hash and _dl_elf_hash) Date: Mon, 25 Apr 2022 10:58:10 -0500 Message-Id: <20220425155814.3558359-2-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220425155814.3558359-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220425155814.3558359-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" If we want to further optimize the functions tests are needed. --- elf/Makefile | 1 + elf/tst-dl-hash.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 148 insertions(+) create mode 100644 elf/tst-dl-hash.c diff --git a/elf/Makefile b/elf/Makefile index 8ed6c3b0b1..493409715e 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -309,6 +309,7 @@ tests := \ tst-array4 \ tst-array5 \ tst-auxv \ + tst-dl-hash \ tst-leaks1 \ tst-stringtable \ tst-tls9 \ diff --git a/elf/tst-dl-hash.c b/elf/tst-dl-hash.c new file mode 100644 index 0000000000..7cbc14b46d --- /dev/null +++ b/elf/tst-dl-hash.c @@ -0,0 +1,147 @@ +/* Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ +/* Simple implementation of ELF ABI hash function. */ + +#include +#include +#include +#include +#include +#include + +typedef unsigned int (*hash_f) (const char *); + +static unsigned int +simple_dl_new_hash (const char *s) +{ + uint32_t h = 5381; + for (unsigned char c = *s; c != '\0'; c = *++s) + h = h * 33 + c; + return h; +} + +static unsigned int +simple_dl_elf_hash (const char *name_arg) +{ + unsigned long int hash = 0; + for (unsigned char c = *name_arg; c != '\0'; c = *(++name_arg)) + { + unsigned long int hi; + hash = (hash << 4) + c; + hi = hash & 0xf0000000; + hash ^= hi >> 24; + hash &= 0x0fffffff; + } + return hash; +} + +static int +do_fill_test (size_t len, int fill, const char *name, hash_f testf, + hash_f expecf) +{ + uint32_t expec, res; + char buf[len + 1]; + memset (buf, fill, len); + buf[len] = '\0'; + + expec = expecf (buf); + res = testf (buf); + if (expec != res) + { + printf ("FAIL: fill(%d) %s(%zu), %x != %x\n", fill, name, len, expec, + res); + return 1; + } + + return 0; +} + +static int +do_fill_tests (size_t len, int fill) +{ + if (do_fill_test (len, fill, "dl_new_hash", &_dl_new_hash, + &simple_dl_new_hash)) + { + return 1; + } + return do_fill_test (len, fill, "dl_elf_hash", &_dl_elf_hash, + &simple_dl_elf_hash); +} + +static int +do_rand_test (size_t len, const char *name, hash_f testf, hash_f expecf) +{ + uint32_t expec, res; + size_t i; + char buf[len + 1]; + char v; + for (i = 0; i < len; ++i) + { + v = random (); + if (v == 0) + { + v = 1; + } + buf[i] = v; + } + buf[len] = '\0'; + + expec = expecf (buf); + res = testf (buf); + if (expec != res) + { + printf ("FAIL: random %s(%zu), %x != %x\n", name, len, expec, res); + return 1; + } + + return 0; +} + +static int +do_rand_tests (size_t len) +{ + if (do_rand_test (len, "dl_new_hash", &_dl_new_hash, &simple_dl_new_hash)) + { + return 1; + } + return do_rand_test (len, "dl_elf_hash", &_dl_elf_hash, &simple_dl_elf_hash); +} + +static int +do_test (void) +{ + size_t i, j; + for (i = 0; i < 100; ++i) + { + for (j = 0; j < 8192; ++j) + { + if (do_rand_tests (i)) + { + return 1; + } + + if (do_fill_tests (i, -1) || do_fill_tests (i, 1) + || do_fill_tests (i, 0x80) || do_fill_tests (i, 0x88)) + { + return 1; + } + } + } + return 0; +} + +#include From patchwork Mon Apr 25 15:58:11 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53194 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7A3AA3858D28 for ; Mon, 25 Apr 2022 16:00:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7A3AA3858D28 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902407; bh=wl6AwBzHS3Nxk7A3acUlPW+0SaIkGnrXOOgsRfsV89s=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=JslEnzkNaYzDXInnzwmxc+EI95OQXdvq+B0oeTxWNaO505n/V4UPEefqkceU+lmJr Qlo3KzDMmTZrMZmlIGgewzLEsKmXHV3OUPH23saDh3lsULSgekVCYXDInu7sH0d0Ym K2IxJyW3NUyj7DZcYDIrvAjUNl2fyFYxwRFW6bWM= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd29.google.com (mail-io1-xd29.google.com [IPv6:2607:f8b0:4864:20::d29]) by sourceware.org (Postfix) with ESMTPS id 793AE3858C53 for ; Mon, 25 Apr 2022 15:58:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 793AE3858C53 Received: by mail-io1-xd29.google.com with SMTP id y85so16346933iof.3 for ; Mon, 25 Apr 2022 08:58:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=wl6AwBzHS3Nxk7A3acUlPW+0SaIkGnrXOOgsRfsV89s=; b=OYcj3hLuHTcO99vXenVUpKaEKjrMitPYAlb7h3mhaWsPC301aMizGkSHOVEiY98+ls cjkNtnp/SFj3WvD4KBN/BdgArSf+7KNuU+D2dVl5Sko9cHh3s74At9RZOr4W5CPrrQeh NmCtgjAuKt/u8+9M1cDvQmLZlTTbBGe3B05+J4vf3i5ciSDFxzxEGo1cOaZByqGCo9YA /3AtYHp/67z/s+IIgPHzRlbkOh9/Ps6kIb+OQ3+azvN3aFmAUepcmtmteT7dBcCQYKUS uXxTzahDlhwSyQi0QYiMJY2EGZVJoKeSX0D4twD9jQl+uGeVT68mzdVka4pQYjRH57uv Tg+w== X-Gm-Message-State: AOAM533hZNDbSAIHrKrHtIHuWBbRdpOiixz0vab5BsaVwqa19aO++QKY ++EZFsUmL6Z1kNIGZ1GzcSKCBvG1j8s= X-Google-Smtp-Source: ABdhPJz+86jHUQZlfTktlKdiXAyEXDb6Cjt2dLhbtMxMUSurHuzHQ5OnpMKKJReBV1gsi0ltM6m7FA== X-Received: by 2002:a05:6638:1388:b0:328:9415:872b with SMTP id w8-20020a056638138800b003289415872bmr8473798jad.236.1650902301731; Mon, 25 Apr 2022 08:58:21 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:21 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 3/6] nss: Add tests for the nss_hash in nss_hash.h Date: Mon, 25 Apr 2022 10:58:11 -0500 Message-Id: <20220425155814.3558359-3-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220425155814.3558359-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220425155814.3558359-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" If we want to further optimize the function tests are needed. --- nss/Makefile | 1 + nss/tst-nss-hash.c | 105 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 106 insertions(+) create mode 100644 nss/tst-nss-hash.c diff --git a/nss/Makefile b/nss/Makefile index d8b06b44fb..a978e3927a 100644 --- a/nss/Makefile +++ b/nss/Makefile @@ -62,6 +62,7 @@ tests := \ test-digits-dots \ test-netdb \ tst-nss-getpwent \ + tst-nss-hash \ tst-nss-test1 \ tst-nss-test2 \ tst-nss-test4 \ diff --git a/nss/tst-nss-hash.c b/nss/tst-nss-hash.c new file mode 100644 index 0000000000..a1f42e3fbc --- /dev/null +++ b/nss/tst-nss-hash.c @@ -0,0 +1,105 @@ +/* Test __nss_hash + Copyright (C) 2017-2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include + +uint32_t __nss_hash (const void *__key, size_t __length); + +/* Simplist implementation of __nss_hash. */ +static uint32_t +simple_nss_hash (const void *keyarg, size_t len) +{ + const unsigned char *key; + size_t i; + uint32_t h = 0; + key = keyarg; + + for (i = 0; i < len; ++i) + { + h = *key++ + 65599 * h; + } + return h; +} + +static int +do_fill_tests (size_t len, int fill) +{ + uint32_t expec, res; + char buf[len]; + memset (buf, fill, len); + + expec = simple_nss_hash (buf, len); + res = __nss_hash (buf, len); + if (expec != res) + { + printf ("FAIL: fill(%d) (%zu), %x != %x\n", fill, len, expec, res); + return 1; + } + + return 0; +} + +static int +do_rand_tests (size_t len) +{ + uint32_t expec, res; + size_t i; + char buf[len]; + for (i = 0; i < len; ++i) + { + buf[i] = random (); + } + + expec = simple_nss_hash (buf, len); + res = __nss_hash (buf, len); + if (expec != res) + { + printf ("FAIL: random (%zu), %x != %x\n", len, expec, res); + return 1; + } + + return 0; +} + +static int +do_test (void) +{ + size_t i, j; + for (i = 0; i < 100; ++i) + { + for (j = 0; j < 8192; ++j) + { + if (do_rand_tests (i)) + { + return 1; + } + if (do_fill_tests (i, -1) || do_fill_tests (i, 1) + || do_fill_tests (i, 0x80) || do_fill_tests (i, 0x88)) + { + return 1; + } + } + } + return 0; +} + +#include From patchwork Mon Apr 25 15:58:12 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53196 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C4FA1385801E for ; Mon, 25 Apr 2022 16:01:36 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C4FA1385801E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902496; bh=rsyFTAlf/PrGB4/sJpnkSREwk3Olkln2SNU2dJjOXTo=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=TC1bYChm2Cgj6+Cxl/IdMWKUu6n7WX2Q9GXG5xYxESJWW8HuUNfBKXuOWDJia41gp 8R0hKW52Fq4QcOi8JxjFEZ6fjXzGhnlwbfzAHhpmokTjF/f4SiZmwT3o1SW8/kDZA2 Y9epQgneXStCZ9nVotqpjDFnxDoSNcL+sVPtl33w= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x130.google.com (mail-il1-x130.google.com [IPv6:2607:f8b0:4864:20::130]) by sourceware.org (Postfix) with ESMTPS id D38C73858D28 for ; Mon, 25 Apr 2022 15:58:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D38C73858D28 Received: by mail-il1-x130.google.com with SMTP id r11so9637981ila.1 for ; Mon, 25 Apr 2022 08:58:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=rsyFTAlf/PrGB4/sJpnkSREwk3Olkln2SNU2dJjOXTo=; b=BxMC+vemieq5imRbSiJIWhA8mv6MkxaS77BvSc/yAqqdz2Ato2mDN9N1+hHDskJ9Y8 c+qW2hyZZk/o96EzOalL5IdIcUK9y67NZKTc4pKwp7xF2ae/iaSn8XHUJp3PgYXliQ6n F5++FGEa0FtTsBZPQfIsez2M+ermPda+zwhMf33TmasB/ZEKTN2RNlJT+oE43kp6mrwg lmlMgqfpBMeaifIMxIzFpVbKIfvmQ9uVRKtgXoewrC7Bjyq+GXvjItT2A2yTmv+WiqOe hTy32+xox81V/rI/pRtf8g5whCG8lNy5oMxBVArLNpc+Q8FZ5i3oTCtEULAaShmQYHFH HvCQ== X-Gm-Message-State: AOAM532fs72hB2yPEHbveP1Pbgxlr+ZnXR/B7dskOZQslbfOb0NP05K1 TOkpLKO/ueYC4CtWSzcXcjJwtUPXBJ0= X-Google-Smtp-Source: ABdhPJzAZ+dRIiKTBLEbecEmAuXOCIGvwUOPbTb2vm/BgaI0VuIJIl468HV/IYpqa97VJYYsI9Axuw== X-Received: by 2002:a05:6e02:1bcd:b0:2cd:650b:db4b with SMTP id x13-20020a056e021bcd00b002cd650bdb4bmr7623402ilv.254.1650902302819; Mon, 25 Apr 2022 08:58:22 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:22 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 4/6] benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash Date: Mon, 25 Apr 2022 10:58:12 -0500 Message-Id: <20220425155814.3558359-4-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220425155814.3558359-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220425155814.3558359-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Benchtests are for throughput and include random / fixed size benchmarks. --- benchtests/Makefile | 25 ++++- benchtests/README | 9 +- benchtests/bench-dl-elf-hash.c | 23 ++++ benchtests/bench-dl-new-hash.c | 23 ++++ benchtests/bench-hash-funcs.c | 196 +++++++++++++++++++++++++++++++++ benchtests/bench-nss-hash.c | 24 ++++ 6 files changed, 292 insertions(+), 8 deletions(-) create mode 100644 benchtests/bench-dl-elf-hash.c create mode 100644 benchtests/bench-dl-new-hash.c create mode 100644 benchtests/bench-hash-funcs.c create mode 100644 benchtests/bench-nss-hash.c diff --git a/benchtests/Makefile b/benchtests/Makefile index 8dfca592fd..aa508a6c4f 100644 --- a/benchtests/Makefile +++ b/benchtests/Makefile @@ -230,6 +230,12 @@ LOCALES := \ include ../gen-locales.mk endif +hash-benchset := \ + dl-elf-hash \ + dl-new-hash \ + nss-hash \ +# hash-benchset + stdlib-benchset := strtod stdio-common-benchset := sprintf @@ -238,7 +244,7 @@ math-benchset := math-inlines ifeq (${BENCHSET},) benchset := $(string-benchset-all) $(stdlib-benchset) $(stdio-common-benchset) \ - $(math-benchset) + $(math-benchset) $(hash-benchset) else benchset := $(foreach B,$(filter %-benchset,${BENCHSET}), ${${B}}) endif @@ -357,9 +363,20 @@ bench-clean: # Validate the passed in BENCHSET ifneq ($(strip ${BENCHSET}),) -VALIDBENCHSETNAMES := bench-pthread bench-math bench-string string-benchset \ - wcsmbs-benchset stdlib-benchset stdio-common-benchset math-benchset \ - malloc-thread malloc-simple +VALIDBENCHSETNAMES := \ + bench-math \ + bench-pthread \ + bench-string \ + hash-benchset \ + malloc-simple \ + malloc-thread \ + math-benchset \ + stdio-common-benchset \ + stdlib-benchset \ + string-benchset \ + wcsmbs-benchset \ +# VALIDBENCHSETNAMES + INVALIDBENCHSETNAMES := $(filter-out ${VALIDBENCHSETNAMES},${BENCHSET}) ifneq (${INVALIDBENCHSETNAMES},) $(info The following values in BENCHSET are invalid: ${INVALIDBENCHSETNAMES}) diff --git a/benchtests/README b/benchtests/README index 4d83a05b4b..998ba9b2b4 100644 --- a/benchtests/README +++ b/benchtests/README @@ -84,12 +84,13 @@ where BENCHSET may be a space-separated list of the following values: bench-math bench-pthread bench-string + hash-benchset + malloc-thread + math-benchset + stdio-common-benchset + stdlib-benchset string-benchset wcsmbs-benchset - stdlib-benchset - stdio-common-benchset - math-benchset - malloc-thread Adding a function to benchtests: =============================== diff --git a/benchtests/bench-dl-elf-hash.c b/benchtests/bench-dl-elf-hash.c new file mode 100644 index 0000000000..5ca5116ad3 --- /dev/null +++ b/benchtests/bench-dl-elf-hash.c @@ -0,0 +1,23 @@ +/* Measure __dl_new_hash runtime + Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#define TEST_FUNC(x, y) _dl_elf_hash (x) +#define TEST_NAME "_dl_elf_hash" + +#include "bench-hash-funcs.c" diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c new file mode 100644 index 0000000000..f5be528960 --- /dev/null +++ b/benchtests/bench-dl-new-hash.c @@ -0,0 +1,23 @@ +/* Measure __dl_new_hash runtime + Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#define TEST_FUNC(x, y) _dl_new_hash (x) +#define TEST_NAME "_dl_new_hash" + +#include "bench-hash-funcs.c" diff --git a/benchtests/bench-hash-funcs.c b/benchtests/bench-hash-funcs.c new file mode 100644 index 0000000000..85cf7de8bc --- /dev/null +++ b/benchtests/bench-hash-funcs.c @@ -0,0 +1,196 @@ +/* Measure hash functions runtime. + Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#define TEST_MAIN +#ifndef TEST_FUNC +# error "No TEST_FUNC provided!" +#endif + +#ifndef TEST_NAME +# define STRINGIFY_PRIMITIVE(x) # x +# define STRINGIFY(x) STRINGIFY_PRIMITIVE (x) + +# define TEST_NAME STRINGIFY (TEST_FUNC) +#endif + +#include "json-lib.h" +#include "bench-timing.h" + +#include +#include +#include + +#define DO_NOT_OPTIMIZE_OUT(x) __asm__ volatile("" : : "r,m"(x) : "memory") + +enum +{ + NFIXED_ITERS = 1048576, + NRAND_BUFS = 16384, + NRAND_ITERS = 2048, + RAND_BENCH_MAX_LEN = 256 +}; + +static double __attribute__ ((noinline, noclone)) +do_one_test_kernel (const char *s, size_t len) +{ + + unsigned int iters; + timing_t start, stop, cur; + + /* Warmup. */ + for (iters = NFIXED_ITERS / 32; iters; --iters) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (s, len)); + } + + TIMING_NOW (start); + for (iters = NFIXED_ITERS; iters; --iters) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (s, len)); + } + TIMING_NOW (stop); + + TIMING_DIFF (cur, start, stop); + + (void) (len); + return (double) cur / (double) NFIXED_ITERS; +} + +static void +do_one_test (json_ctx_t *json_ctx, size_t len) +{ + char buf[len + 1]; + memset (buf, -1, len); + buf[len] = '\0'; + + json_element_object_begin (json_ctx); + + json_attr_string (json_ctx, "type", "fixed"); + json_attr_uint (json_ctx, "length", len); + json_attr_double (json_ctx, "time", do_one_test_kernel (buf, len)); + + json_element_object_end (json_ctx); +} +static double +do_rand_test_kernel (char const *bufs, unsigned int const *sizes) +{ + unsigned int i, iters; + size_t offset; + timing_t start, stop, cur; + + /* Warmup. */ + for (i = 0, offset = 0; i < NRAND_BUFS; ++i, offset += RAND_BENCH_MAX_LEN) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (bufs + offset, sizes[i])); + } + + TIMING_NOW (start); + for (iters = NRAND_ITERS; iters; --iters) + { + for (i = 0, offset = 0; i < NRAND_BUFS; + ++i, offset += RAND_BENCH_MAX_LEN) + { + DO_NOT_OPTIMIZE_OUT (TEST_FUNC (bufs + offset, sizes[i])); + } + } + TIMING_NOW (stop); + + TIMING_DIFF (cur, start, stop); + + (void) (sizes); + return (double) cur / (double) (NRAND_ITERS * NRAND_BUFS); +} + +static void __attribute__ ((noinline, noclone)) +do_rand_test (json_ctx_t *json_ctx) +{ + size_t i, sz, offset; + char *bufs; + unsigned int *sizes; + + bufs = (char *) calloc (NRAND_BUFS, RAND_BENCH_MAX_LEN); + sizes = (unsigned int *) calloc (NRAND_BUFS, sizeof (unsigned int)); + if (bufs == NULL || sizes == NULL) + { + fprintf (stderr, "Failed to allocate bufs for random test\n"); + goto done; + } + + for (sz = 2; sz <= RAND_BENCH_MAX_LEN; sz += sz) + { + json_element_object_begin (json_ctx); + json_attr_string (json_ctx, "type", "random"); + json_attr_uint (json_ctx, "length", sz); + + for (i = 0, offset = 0; i < NRAND_BUFS; + ++i, offset += RAND_BENCH_MAX_LEN) + { + sizes[i] = random () % sz; + memset (bufs + offset, -1, sizes[i]); + bufs[offset + sizes[i]] = '\0'; + } + + json_attr_double (json_ctx, "time", do_rand_test_kernel (bufs, sizes)); + json_element_object_end (json_ctx); + } + +done: + if (bufs) + { + free (bufs); + } + if (sizes) + { + free (sizes); + } +} + +static int +do_test (void) +{ + int i; + json_ctx_t json_ctx; + + json_init (&json_ctx, 0, stdout); + json_document_begin (&json_ctx); + json_attr_string (&json_ctx, "timing_type", TIMING_TYPE); + json_attr_object_begin (&json_ctx, "functions"); + json_attr_object_begin (&json_ctx, TEST_NAME); + json_array_begin (&json_ctx, "results"); + + for (i = 0; i < 16; ++i) + { + do_one_test (&json_ctx, i); + } + + for (i = 16; i <= 256; i += i) + { + do_one_test (&json_ctx, i); + } + + do_rand_test (&json_ctx); + + json_array_end (&json_ctx); + json_attr_object_end (&json_ctx); + json_attr_object_end (&json_ctx); + json_document_end (&json_ctx); + + return 0; +} + +#include diff --git a/benchtests/bench-nss-hash.c b/benchtests/bench-nss-hash.c new file mode 100644 index 0000000000..085e1f8ee2 --- /dev/null +++ b/benchtests/bench-nss-hash.c @@ -0,0 +1,24 @@ +/* Measure __nss_hash runtime + Copyright (C) 2022 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#define TEST_FUNC __nss_hash + +uint32_t __nss_hash (const void *__key, size_t __length); + +#include "bench-hash-funcs.c" From patchwork Mon Apr 25 15:58:13 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53195 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0A9D7385840C for ; Mon, 25 Apr 2022 16:00:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0A9D7385840C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902455; bh=zj2NFHnTeLyhxkSHLGu3uAgkctu3K3V0M2ge6pbE41w=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=LWI0GsvSO6YiBUtwaavYigh4OIcHzIYBnouB99HKhSy6L0InC+wdpWNoFYMN0H5rN ulI8CtFKRQCcAHyLGZ+ziub2TnpPGXNlLfkV6rN5I/lxeCi/rXuXBe0pLlKCkYTwYE PaWGCHu6yhE9bulVUF/KGgVj3zApbycf3kjt0TKY= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2d.google.com (mail-io1-xd2d.google.com [IPv6:2607:f8b0:4864:20::d2d]) by sourceware.org (Postfix) with ESMTPS id 455C63858C83 for ; Mon, 25 Apr 2022 15:58:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 455C63858C83 Received: by mail-io1-xd2d.google.com with SMTP id n134so16303859iod.5 for ; Mon, 25 Apr 2022 08:58:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=zj2NFHnTeLyhxkSHLGu3uAgkctu3K3V0M2ge6pbE41w=; b=hOOi/Catz5d4a1dUZVUgNgnq7/mzm0YhC6Odc9WTjzBvgO2h3KSRjciKGBiQzOfslG rbfK6mR/VWZiNk0Zgpke4lulXxSYle7dsRbFmW9RMcLTx6iJKt6KXbYEIM+yy/b/b2f+ 1SZp+z0NY8uVKUj9HnVqFyu/dhpyPDohCO/FI5SJbidNt0y6AplMg8/OmiFhXo+XE3DA Y/W/P4jFLpg63nnyQojss8HlaVtChIZ7Kxt23H+zWOoeHGsZkEKUeQharIc/fHvuq+6M 0IUTg6Y34dx8LcDBBim6WJjyNlOiivnYnXy+tfk993Bx6FRtAVSFbWOqGnnMwPuwQ/T1 v7sw== X-Gm-Message-State: AOAM530kU29jXO/p4Io08NITI3dpM7p9gD59wzO7sbMoOn0Pvc41N+Vp W8VuEdXtRbM9nN19OQUlwFLf2OyA5vg= X-Google-Smtp-Source: ABdhPJyDTFEbsOpQtWnkD/OzAn8Akbb/IrodW+LI4GNUuQkraRg3rVvlAXWYfvheeV8fn/WUx0P0+A== X-Received: by 2002:a05:6602:1544:b0:656:62f9:d237 with SMTP id h4-20020a056602154400b0065662f9d237mr7303474iow.189.1650902303492; Mon, 25 Apr 2022 08:58:23 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:23 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 5/6] nss: Optimize nss_hash in nss_hash.c Date: Mon, 25 Apr 2022 10:58:13 -0500 Message-Id: <20220425155814.3558359-5-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220425155814.3558359-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220425155814.3558359-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-10.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, LIKELY_SPAM_BODY, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" The prior unrolling didn't really do much as it left the dependency chain between iterations. Unrolled the loop for 4 so 4x multiplies could be pipelined in out-of-order machines. Results for __nss_hash Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz Time as Geometric Mean of N=25 runs Geometric of all benchmark New / Old: 0.845 type, length, New Time, Old Time, New Time / Old Time fixed, 0, 4.019, 3.729, 1.078 fixed, 1, 4.95, 5.707, 0.867 fixed, 2, 5.152, 5.657, 0.911 fixed, 3, 4.641, 5.721, 0.811 fixed, 4, 5.551, 5.81, 0.955 fixed, 5, 6.525, 6.552, 0.996 fixed, 6, 6.711, 6.561, 1.023 fixed, 7, 6.715, 6.767, 0.992 fixed, 8, 7.874, 7.915, 0.995 fixed, 9, 8.888, 9.767, 0.91 fixed, 10, 8.959, 9.762, 0.918 fixed, 11, 9.188, 9.987, 0.92 fixed, 12, 9.708, 10.618, 0.914 fixed, 13, 10.393, 11.14, 0.933 fixed, 14, 10.628, 12.097, 0.879 fixed, 15, 10.982, 12.965, 0.847 fixed, 16, 11.851, 14.429, 0.821 fixed, 32, 24.334, 34.414, 0.707 fixed, 64, 55.618, 86.688, 0.642 fixed, 128, 118.261, 224.36, 0.527 fixed, 256, 256.183, 538.629, 0.476 random, 2, 11.194, 11.556, 0.969 random, 4, 17.516, 17.205, 1.018 random, 8, 23.501, 20.985, 1.12 random, 16, 28.131, 29.212, 0.963 random, 32, 35.436, 38.662, 0.917 random, 64, 45.74, 58.868, 0.777 random, 128, 75.394, 121.963, 0.618 random, 256, 139.524, 260.726, 0.535 --- nss/nss_hash.c | 79 +++++++++++++++++++++++++++----------------------- 1 file changed, 42 insertions(+), 37 deletions(-) diff --git a/nss/nss_hash.c b/nss/nss_hash.c index 27a348ea9b..c6a375f386 100644 --- a/nss/nss_hash.c +++ b/nss/nss_hash.c @@ -19,58 +19,63 @@ /* This is from libc/db/hash/hash_func.c, hash3 is static there */ /* - * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte + * This is INCREDIBLY ugly, but fast. We break the string up into 4 byte * units. On the first time through the loop we get the "leftover bytes" - * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle - * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If - * this routine is heavily used enough, it's worth the ugly coding. + * (len % 4). On every other iteration, we perform a 4x unrolled version + * HASHC. Further unrolling does not appear to help. * * OZ's original sdbm hash */ uint32_t __nss_hash (const void *keyarg, size_t len) { + enum + { + HASH_CONST_P0 = 1, /* (uint32_t)(65599 ^ 0). */ + HASH_CONST_P1 = 65599, /* (uint32_t)(65599 ^ 1). */ + HASH_CONST_P2 = 8261505, /* (uint32_t)(65599 ^ 2). */ + HASH_CONST_P3 = 780587199, /* (uint32_t)(65599 ^ 3). */ + HASH_CONST_P4 = 1139564289 /* (uint32_t)(65599 ^ 4). */ + }; + const unsigned char *key; - size_t loop; uint32_t h; -#define HASHC h = *key++ + 65599 * h +#define HASHC h = *key++ + HASH_CONST_P1 * h h = 0; key = keyarg; if (len > 0) { - loop = (len + 8 - 1) >> 3; - switch (len & (8 - 1)) - { - case 0: - do - { - HASHC; - /* FALLTHROUGH */ - case 7: - HASHC; - /* FALLTHROUGH */ - case 6: - HASHC; - /* FALLTHROUGH */ - case 5: - HASHC; - /* FALLTHROUGH */ - case 4: - HASHC; - /* FALLTHROUGH */ - case 3: - HASHC; - /* FALLTHROUGH */ - case 2: - HASHC; - /* FALLTHROUGH */ - case 1: - HASHC; - } - while (--loop); - } + switch ((len & (4 - 1))) + { + case 0: + /* h starts out as zero so no need to include the multiply. */ + h = *key++; + /* FALLTHROUGH */ + case 3: + HASHC; + /* FALLTHROUGH */ + case 2: + HASHC; + /* FALLTHROUGH */ + case 1: + HASHC; + /* FALLTHROUGH */ + } + + uint32_t c0, c1, c2, c3; + for (--len; len >= 4; len -= 4) + { + c0 = (unsigned char) *(key + 0); + c1 = (unsigned char) *(key + 1); + c2 = (unsigned char) *(key + 2); + c3 = (unsigned char) *(key + 3); + h = HASH_CONST_P4 * h + HASH_CONST_P3 * c0 + HASH_CONST_P2 * c1 + + HASH_CONST_P1 * c2 + HASH_CONST_P0 * c3; + + key += 4; + } } return h; } From patchwork Mon Apr 25 15:58:14 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 53197 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6D1993857820 for ; Mon, 25 Apr 2022 16:02:19 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6D1993857820 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1650902539; bh=ayvLBWaAmUglkXeAb9jA6PrIj3L3vSsibSoKqZXxkDY=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=Z/vZvGUW0jXfklGKj4RI3BZUIAiWEIgZgc+7Pu4YlSqN4yBmNVI0Icy1qaXLw1m1x 02RdPQcraEOP8sc7/RLB/2OiOsKpN7UBwudRDUXtp+TWuR2PdWHsYJ4h0XhOaNTrhU Wzs9QUC9RQsVO8+UL1VEznTQvhDFDFdg2ECM5KEY= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2c.google.com (mail-io1-xd2c.google.com [IPv6:2607:f8b0:4864:20::d2c]) by sourceware.org (Postfix) with ESMTPS id 8AD5E385842E for ; Mon, 25 Apr 2022 15:58:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8AD5E385842E Received: by mail-io1-xd2c.google.com with SMTP id e194so16290984iof.11 for ; Mon, 25 Apr 2022 08:58:25 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=ayvLBWaAmUglkXeAb9jA6PrIj3L3vSsibSoKqZXxkDY=; b=pC53cIaebZDICqJL5vq4RglRxnmmCcLYNGyITIOTowYu5KWEC10TGNjEYcgukkTvWw yzl9XiU/Kh3DF+4gw+cEaqJZw88u/XxaGQed1Il0KUA77/oqOTscAtm52R9GlfWEDolY IiBg+TLXR8A/YXvmainZDNJOHR9A9/VjrjxGoB1xv4fJd/FSgNcDTkj/PI54T8M0VQVK rjqc3Co5tjASkXZTxwLt6mZCq4uZsdaJmHYpGiFhVfl7GnMK5FQRxfYaKUqbyB1Jydyf QWyvaszAuY3u4jXOkuy5HfYuMIDbnxo2AcUbGe/74laAeK44HNjbnoYpyhvbmDFjMAbj Dumw== X-Gm-Message-State: AOAM530oCmPL1CsB+PtYkjp32FISAsH0FSaqBisIru7PRKKUFNNM1l32 VgURRF+0WkpGQEFa4E/20jpV24nJrng= X-Google-Smtp-Source: ABdhPJwPZNI8eCthOc8kQrTpdslaxBKixhmO0yvB+HgCJoB4oM2u6QzJauYyeMyqsskvm5zNL25M3g== X-Received: by 2002:a6b:ee12:0:b0:64d:2f8f:15bb with SMTP id i18-20020a6bee12000000b0064d2f8f15bbmr7155853ioh.16.1650902304758; Mon, 25 Apr 2022 08:58:24 -0700 (PDT) Received: from localhost.localdomain ([173.245.202.37]) by smtp.googlemail.com with ESMTPSA id d3-20020a056e020c0300b002c7b42b4b0esm6519897ile.65.2022.04.25.08.58.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Apr 2022 08:58:24 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v3 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Mon, 25 Apr 2022 10:58:14 -0500 Message-Id: <20220425155814.3558359-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220425155814.3558359-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220425155814.3558359-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Unroll slightly so some of the multiples can be pipelined on out-order machines. Unrolling further started to induce slowdowns for sizes [0, 4] but can help the loop so if larger sizes are the target further unrolling can be beneficial. Results for _dl_new_hash Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz Time as Geometric Mean of N=25 runs Geometric of all benchmark New / Old: 0.791 type, length, New Time, Old Time, New Time / Old Time fixed, 0, 0.641, 0.658, 0.974 fixed, 1, 1.888, 1.883, 1.003 fixed, 2, 2.712, 2.833, 0.957 fixed, 3, 3.314, 3.739, 0.886 fixed, 4, 4.316, 4.866, 0.887 fixed, 5, 5.16, 5.966, 0.865 fixed, 6, 5.986, 7.241, 0.827 fixed, 7, 7.264, 8.435, 0.861 fixed, 8, 8.052, 9.846, 0.818 fixed, 9, 9.369, 11.316, 0.828 fixed, 10, 10.256, 12.925, 0.794 fixed, 11, 12.191, 14.546, 0.838 fixed, 12, 12.667, 15.92, 0.796 fixed, 13, 14.442, 17.465, 0.827 fixed, 14, 14.808, 18.981, 0.78 fixed, 15, 16.244, 20.565, 0.79 fixed, 16, 17.166, 22.044, 0.779 fixed, 32, 35.447, 50.558, 0.701 fixed, 64, 86.479, 134.529, 0.643 fixed, 128, 155.453, 287.527, 0.541 fixed, 256, 302.57, 593.64, 0.51 random, 2, 11.168, 10.61, 1.053 random, 4, 13.308, 13.53, 0.984 random, 8, 16.579, 19.437, 0.853 random, 16, 21.292, 24.776, 0.859 random, 32, 30.56, 35.906, 0.851 random, 64, 49.249, 68.577, 0.718 random, 128, 81.845, 140.664, 0.582 random, 256, 152.517, 292.204, 0.522 --- elf/dl-new-hash.h | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) diff --git a/elf/dl-new-hash.h b/elf/dl-new-hash.h index 52eef4e417..b0026706bd 100644 --- a/elf/dl-new-hash.h +++ b/elf/dl-new-hash.h @@ -20,14 +20,33 @@ #define _DL_NEW_HASH_H 1 #include +/* For __glibc_unlikely. */ +#include static uint32_t +__attribute__ ((unused)) _dl_new_hash (const char *s) { - uint32_t h = 5381; - for (unsigned char c = *s; c != '\0'; c = *++s) - h = h * 33 + c; - return h; + unsigned int h = 5381; + unsigned char c0, c1; + for (;;) + { + c0 = *s; + /* Unlikely length zero string so evens will be slightly less + common. */ + if (__glibc_unlikely (c0 == 0)) + { + return h; + } + + c1 = *(s + 1); + if (c1 == 0) + { + return h * 33 + c0; + } + h = 33 * 33 * h + 33 * c0 + c1; + s += 2; + } }