From patchwork Tue May 10 15:04:36 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629206 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=gERxbCIt; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KyLvH6ZBsz9sG6 for ; Wed, 11 May 2022 01:05:31 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5A7193955CAA for ; Tue, 10 May 2022 15:05:29 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5A7193955CAA DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652195129; bh=JzjCNBBxCDu4ubEn2FppLBMbRFL2uIeLcqaS5dVxwNs=; 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=gERxbCItd/7icJnuOAIH9TgrKYjsTSwfqa5mkSc4zBJi9gCldfFggbNR+H4U5pL03 5YM5pOK39V2ErL9sRaebCESGC1hVwnA01/+Xio2oJSBX989mJPI91XQGSgAjELiOlg /xX/U8HROMumnkhr5ySas8eSuMkcXOmwbhLYJqS4= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd32.google.com (mail-io1-xd32.google.com [IPv6:2607:f8b0:4864:20::d32]) by sourceware.org (Postfix) with ESMTPS id 636EF3955CA1 for ; Tue, 10 May 2022 15:04:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 636EF3955CA1 Received: by mail-io1-xd32.google.com with SMTP id m6so18802718iob.4 for ; Tue, 10 May 2022 08:04:47 -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=JzjCNBBxCDu4ubEn2FppLBMbRFL2uIeLcqaS5dVxwNs=; b=cPsKQiQA624BPml6zdo3yZkhnG4kesBch3v8ccKw1AOsVW0HkE1X8YJIL+o9vuydyz jpbCKsAqbNk6WrsN72X1vZTwbJ7hy/ADA/qMDMEjc4fAW6zjodU5h926u5+NZzRAiYwY T4s8O4AqlJ/tJIfnW2c6hHD/6y+5lQ2MVuyNZ8f6bllBIdr3Jet0oLtSYHtgwWKVf/t/ Kx4tJn1igtlj1oOta/caYTnmctZ8IkPb93H47v8cmu7hhHOD1ByVULoSYB16f2QzoZns CWN2BW9jtXqfiGyf7CsjmjrjVZ4GMMA7hZQdnNEhM+KQRZN3hi2Tl6qXob0rGYvHXBeu cNSg== X-Gm-Message-State: AOAM533MHRK882czJCjEObcbVbGI/pJomjpBctys+QT3x982MxRz9E4l rglDqyRkiN8bveaLSNpT8Q0z+h7OwLI= X-Google-Smtp-Source: ABdhPJyTEl7Ir3HsKIGnDeSNYa66VQQ+oF7y12KrwS32r5sb5lJapyzPkcm2ZLbxuJpsWdCpVFhWSg== X-Received: by 2002:a05:6638:dc6:b0:32b:8f90:ea9a with SMTP id m6-20020a0566380dc600b0032b8f90ea9amr10127020jaj.177.1652195086458; Tue, 10 May 2022 08:04:46 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id i11-20020a5e850b000000b0065a47e16f62sm4288988ioj.52.2022.05.10.08.04.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 08:04:46 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v6 1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked Date: Tue, 10 May 2022 10:04:36 -0500 Message-Id: <20220510150441.20948-1-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.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=-12.3 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, T_SCC_BODY_TEXT_LINE 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+incoming=patchwork.ozlabs.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 | 35 +++++++++++++++++++++++++++++++++++ 2 files changed, 37 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..40d88c81f9 --- /dev/null +++ b/elf/dl-new-hash.h @@ -0,0 +1,35 @@ +/* _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 inline 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; +} + + +#endif /* dl-new-hash.h */ From patchwork Tue May 10 15:04:37 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629207 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=MzK0qaRI; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KyLw508H2z9sG6 for ; Wed, 11 May 2022 01:06:13 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id D8E6F3955CB4 for ; Tue, 10 May 2022 15:06:10 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D8E6F3955CB4 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652195170; bh=INESi4Aya2/d5IDfMOohAB4YqjtCDNvnWiYOMQ7ovAg=; 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=MzK0qaRI8miDOEslmbdiTnR9b4RIz/jk0jHFGBxl2Q7bpjX/m3Mc+CAvEdEh1NBDP ZEytn+KXJWACxckOCaXAC5sFwLHUr5itcFTLCmgoPE4r5trd8Hd2RBUf28rruqRbir Z2EH82J3eA1MtpE+CDOHlh6SPNJN6ME70/G+WJXY= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x134.google.com (mail-il1-x134.google.com [IPv6:2607:f8b0:4864:20::134]) by sourceware.org (Postfix) with ESMTPS id 282B43959C48 for ; Tue, 10 May 2022 15:04:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 282B43959C48 Received: by mail-il1-x134.google.com with SMTP id d3so11537709ilr.10 for ; Tue, 10 May 2022 08:04:48 -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=INESi4Aya2/d5IDfMOohAB4YqjtCDNvnWiYOMQ7ovAg=; b=pYLuc4emSNzchlwv5XukqbSoAbebPaMUB1572i4uhHc+ha/EVGH/UFovKK4HtTY5pN OTGQUAZ9KUBS8SyqEunyLP19+TrQYTGPk7gMmYTbrPek9FAPPAq+WfVROVRoBOx7Gis3 gEq4TDM4WIwAQkNQivttEJ55NT9YI9JQxEu8YolYqbZBZpJxSMK92vFgBCmIyrmgKTFY 8E288Z954pFHUY3nWaS8MgJrnFxEGkX+Zyl2GYpz813UXZJQt2UH6oiIwKGlV3HoLOHr o4rx+7TY1lq/Sx0vm9i0wrFzbFW8eW11byjMAsEwR9/jczonKotdD1TACpS6F5xwCKdj TJJQ== X-Gm-Message-State: AOAM531P7r/mayb4oDthXoYpBUfn+i5JFD0CTf4HEdeH67Uu5/Guc5vD WRFxHYsjEvUnVPPVbLtpVfxdsF/9Sic= X-Google-Smtp-Source: ABdhPJxbLdURP48vOh9OpNq26+9mKvQXPGUPC3cAIQkAJnHAp6LcZ6sYROTlzYw8Kq52Y3PpkHkkig== X-Received: by 2002:a05:6e02:10d4:b0:2ca:c81f:5013 with SMTP id s20-20020a056e0210d400b002cac81f5013mr9208849ilj.262.1652195087247; Tue, 10 May 2022 08:04:47 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id i11-20020a5e850b000000b0065a47e16f62sm4288988ioj.52.2022.05.10.08.04.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 08:04:47 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v6 2/6] elf: Add tests for the dl hash funcs (_dl_new_hash and _dl_elf_hash) Date: Tue, 10 May 2022 10:04:37 -0500 Message-Id: <20220510150441.20948-2-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510150441.20948-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510150441.20948-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 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, T_SCC_BODY_TEXT_LINE 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+incoming=patchwork.ozlabs.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 fc9860edee..0e72f913a0 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..e806a274ca --- /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 +#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) + { + FAIL_EXIT1 ("FAIL: fill(%d) %s(%zu), %x != %x\n", fill, name, len, expec, + res); + } + + 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 Tue May 10 15:04:38 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629208 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=vklrYrJC; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KyLx014zzz9sG6 for ; Wed, 11 May 2022 01:07:00 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0E30A3955C97 for ; Tue, 10 May 2022 15:06:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0E30A3955C97 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652195218; bh=b85KrNQ58bigCm+8XvDNxoHSJQ+LMSSMUpP3nFipbBY=; 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=vklrYrJCnTVI9iG+R29sAkxg70prRcxk4n8OfU2eiU4eF9ywIGwXkbjHTeC8OBFSA wjH1mkgoHR3i/lyQ9CzXQKC886AF55jLYb2bPw69Oy1EaY+S1QrACrEtVbzyyIuojl O7/qqTGyt1jmoV2yjdWux0iBqHk83F65V1ibUdFw= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x129.google.com (mail-il1-x129.google.com [IPv6:2607:f8b0:4864:20::129]) by sourceware.org (Postfix) with ESMTPS id EC0733955CBD for ; Tue, 10 May 2022 15:04:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EC0733955CBD Received: by mail-il1-x129.google.com with SMTP id f5so11518660ilj.13 for ; Tue, 10 May 2022 08:04:48 -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=b85KrNQ58bigCm+8XvDNxoHSJQ+LMSSMUpP3nFipbBY=; b=L0E1TztQVZbUkdV2PN8umHj/cgX4uBluc3gJKizEAMdXTCANWa/XfkrLL9HJ56AkVH Y6f4ub11am+mtOK/hzCItB97fqE4JFOArj+dP3Qk0mCFd6EI7PwicoHmgBb1CcggMNS7 Au3W2H/Gaxm1IR/ajQTDbHldWtYDEBniXLRJ2AdTm9vMqsesRtX2nLQyquBFey+p1NAz WGOD7Kbt0XIi3XJnSc5tZResLtJJRHSfhl21a7+TdunpCQzKLu/faY4hDiH0OX8QMWES 8MZN4TxXC4qH1K6FI88b61aAIakFgQEMg6cQ/1MDwdblC6dCsO7342q30klQ1wAlUNST 0mlQ== X-Gm-Message-State: AOAM532BL/fW72T/VGNuxCQiJnfwKce+H6aFQR/qc9WEK5plXdHZ0Oi1 2Yd/q5nEZWJDqrUJDmKSIKal+Q4PMaM= X-Google-Smtp-Source: ABdhPJyNqXm4ZxzN8mBAXjZRl5lGQICzbV39UKjMesKqhmInr/QoSwEIlftZliBYIsDJQirKLJQGlA== X-Received: by 2002:a05:6e02:216b:b0:2cf:3f1c:fd63 with SMTP id s11-20020a056e02216b00b002cf3f1cfd63mr9938262ilv.141.1652195088118; Tue, 10 May 2022 08:04:48 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id i11-20020a5e850b000000b0065a47e16f62sm4288988ioj.52.2022.05.10.08.04.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 08:04:47 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v6 3/6] nss: Add tests for the nss_hash in nss_hash.h Date: Tue, 10 May 2022 10:04:38 -0500 Message-Id: <20220510150441.20948-3-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510150441.20948-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510150441.20948-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 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, T_SCC_BODY_TEXT_LINE 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+incoming=patchwork.ozlabs.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..6bb2ce06ab --- /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 +#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) + { + FAIL_EXIT1 ("FAIL: fill(%d) (%zu), %x != %x\n", fill, len, expec, res); + } + + 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 Tue May 10 15:04:39 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629212 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=mXPrBSw4; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KyLyc3Zgyz9sG6 for ; Wed, 11 May 2022 01:08:24 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A170C3955616 for ; Tue, 10 May 2022 15:08:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A170C3955616 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652195301; bh=grGPfx2x1xo+ha8Y0qbF5nV5jzI0dVTiGvop+ctOAcY=; 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=mXPrBSw42p5HFAFIMV1i0/lkK/YQ3dKNBK0wlBt2hNHLA2JE0c5hCN5VV3NargWmK 8w+BoMaRf/bTJpLdLd6mvXDnr8taV8L0vjF1Mj9S8rcjzxoXccLnoSb+UbNTvAfkil i9nCkUzxpIDlpQ4qVO1r6IlT73qLouF9KkoCvkC8= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x129.google.com (mail-il1-x129.google.com [IPv6:2607:f8b0:4864:20::129]) by sourceware.org (Postfix) with ESMTPS id BC2A93955C8E for ; Tue, 10 May 2022 15:04:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BC2A93955C8E Received: by mail-il1-x129.google.com with SMTP id b5so11540323ile.0 for ; Tue, 10 May 2022 08:04:49 -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=grGPfx2x1xo+ha8Y0qbF5nV5jzI0dVTiGvop+ctOAcY=; b=NlZ7PEyr8d43yqLFRo1UkiUY5WwfSbfl/JC/s+EEOab+JxBBMpBQCNgg4ji43fw8Qa TkL7JjQ56Q1JdkYNsotEM5ebCL6GBVlpzh7I63YdRFW0dl/xa6Ya7zqcf+XYQRQf7cri 6+fX+yBHsHzm+xbOvJUEDLPPC3FlCGcQtvWPHL+VQ78B06IEsKlqyrkV8Rqyy3K2l9jS NZ2vnP53fz+bpV8+nVEU6zh4FKhN85GWc71p2y7w8aDX1YA56IG8Ohhe5l5PJC4kAdgW EXsmLtW9hpk/gvsDJhaMC95KntEaPfd7mB33z6fsFaTmPeqskKXHUT2HwNfqz6yGhjHX 8BnA== X-Gm-Message-State: AOAM531EIhlEr0/vyBaJngClKt+/GfBmckikRITBpejI+IDYEm+j9R6/ tLYnV4ZhV/l3HDeZ9GyxvImZy6uYfYM= X-Google-Smtp-Source: ABdhPJy29VfUZj/vQeYSdvg01DM2PiCUpEfoABsfXaDMlyf9DtLitbIV98wKBztkPVQ6fntYZDb/Xw== X-Received: by 2002:a05:6e02:1c23:b0:2cf:6de9:5330 with SMTP id m3-20020a056e021c2300b002cf6de95330mr9705509ilh.246.1652195088880; Tue, 10 May 2022 08:04:48 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id i11-20020a5e850b000000b0065a47e16f62sm4288988ioj.52.2022.05.10.08.04.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 08:04:48 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v6 4/6] benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash Date: Tue, 10 May 2022 10:04:39 -0500 Message-Id: <20220510150441.20948-4-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510150441.20948-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510150441.20948-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 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, T_SCC_BODY_TEXT_LINE 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+incoming=patchwork.ozlabs.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 de9de5cf58..c279041e19 100644 --- a/benchtests/Makefile +++ b/benchtests/Makefile @@ -227,6 +227,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 @@ -235,7 +241,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 @@ -363,9 +369,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 Tue May 10 15:04:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629209 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=APZFUQy6; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KyLxn5H4Kz9sG6 for ; Wed, 11 May 2022 01:07:41 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7A1E73954C4D for ; Tue, 10 May 2022 15:07:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7A1E73954C4D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652195259; bh=8XXwIyepiRR89xe1+sD2xpOrLwdE6RLLzFY6bSfdgDg=; 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=APZFUQy6FAINnMdPRpmaGrxI1v5tT1isFB7COpUvI2cQtla7/i3E+WFyJPCP2XEuJ xTnBSB5y8ym6Mem/8U+3Mvq3/INItaSWqHlzJ0NoKJLUPbOJ0dPEVbYbuScSsCuOJN O+27txFOytWK2WOI2ZUI6ArslnENoo7NcKOQosbQ= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd32.google.com (mail-io1-xd32.google.com [IPv6:2607:f8b0:4864:20::d32]) by sourceware.org (Postfix) with ESMTPS id 22DA03959C44 for ; Tue, 10 May 2022 15:04:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 22DA03959C44 Received: by mail-io1-xd32.google.com with SMTP id m6so18802718iob.4 for ; Tue, 10 May 2022 08:04:50 -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=8XXwIyepiRR89xe1+sD2xpOrLwdE6RLLzFY6bSfdgDg=; b=7XYc1pjTm8pureEwHwABbz4eRzcLTrC87qy50nwoY7Aeb7FSnD/YzdYJwUeFE9Bb9D xwzV5qu9eZitseyJmNB3r0RjryoKb+RWKOs53Xa/a74NogDMjEEhmnZQHaIn9DKqQk2R wU42hvRmfLpogZUuTmAHfZoMIs9uqLofbfEbMBKryikE7YWqx5jpQLKnw7eViw3Oaa1n QX+Eok3oscZz4HtRMIwKlt2V4mG0BQe2m0nMSjQesjtgjUwRsxqhtf3UHcQvB6Ui0u+Z ayWjJTj0p203VBBr3ED1UVMSGCnkz/ZexAgDNSHr43eivjyYdgU5CEI34VCxmWjAQkXe s3EQ== X-Gm-Message-State: AOAM530rtyAn1Ggjr+UNvhLoi9ntpah432i9KFtNlaWL8h676DrNnfET FwyLM3fsO4FXUjS65btQCoRoA8tdEas= X-Google-Smtp-Source: ABdhPJzKO8Gpg2hsnzGaf4AuhuR1WI8wXvLof6B9/yOaRpqZQ/Pj96WkGhDkHoEb2e6WKBs4hOwjXw== X-Received: by 2002:a05:6638:24d6:b0:32b:e72d:1a33 with SMTP id y22-20020a05663824d600b0032be72d1a33mr6798254jat.226.1652195089676; Tue, 10 May 2022 08:04:49 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id i11-20020a5e850b000000b0065a47e16f62sm4288988ioj.52.2022.05.10.08.04.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 08:04:49 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v6 5/6] nss: Optimize nss_hash in nss_hash.c Date: Tue, 10 May 2022 10:04:40 -0500 Message-Id: <20220510150441.20948-5-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510150441.20948-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510150441.20948-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.3 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, T_SCC_BODY_TEXT_LINE 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+incoming=patchwork.ozlabs.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 Tue May 10 15:04:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629214 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=P/gY3jZB; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KyLzP4Zc5z9sG6 for ; Wed, 11 May 2022 01:09:05 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3F3373955CB4 for ; Tue, 10 May 2022 15:09:03 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 3F3373955CB4 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652195343; bh=39ZhwaRnO7izlBsJGP4yq+F8SMNFED7tN4qXak0uZfo=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=P/gY3jZBLcTg9/URBeotmoLBgIBbGADW+ZMUoRoYKCmcZZaa1CFYq3rnPuel1YWma 9FdW3rw+tWn+o0/h9D6AEU0ZQvKMuCZf5Ge8JUMpXXlthBBXfMFlhA/dJvh8aWO5A/ 3070M0oB1Hxgo9v2JKOR/H+IznG0h7AHWO5tqDgU= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2a.google.com (mail-io1-xd2a.google.com [IPv6:2607:f8b0:4864:20::d2a]) by sourceware.org (Postfix) with ESMTPS id 814003955630 for ; Tue, 10 May 2022 15:04:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 814003955630 Received: by mail-io1-xd2a.google.com with SMTP id f4so18807408iov.2 for ; Tue, 10 May 2022 08:04:51 -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=39ZhwaRnO7izlBsJGP4yq+F8SMNFED7tN4qXak0uZfo=; b=MDDjV8P4mOsgITw52TG8aUhFzkppfp+cbm1RPAPcfePPe2lD9zwqjduVlOWBcSA+1D 1XXO6NvDppI9v2XvC5mg3UMPMX2cmhvgHZIxu2sfhHqtB1WLNonrH7I7e/79JOflh0e8 JpDdzP5kWxcI/5+pKmj3NbAGNlDzaJBbpCraK4AQ9LNqDNa01TWW3b5/RUUVkpdaiKRU 4IxJj0uRmjpD+9WsUYfNYjFd1ms+m75Z66r3203EsmTPi3QdIcaBCVc9hWw75+wO0hHv jzdkbrIdj6PQwDB7MA8y6UTHWSnDV5CuK813RvVln5g9HGli9u2wuI4A5Cee1pyPoJG+ qEgw== X-Gm-Message-State: AOAM531nYsTj00H7zytO5KCQk+aL6pe6MdSasfDv3oevqlxlW7vQi2pq lmRdfzf+Sh2W4tbwo36+X+j5GWkGBX8= X-Google-Smtp-Source: ABdhPJwZrD4uU+irbiJ/878OMGDFmA7wVbRGNl4tKnw0HPhRKzgKUpYnENtuVEDfSCgI9CSaBaN+/Q== X-Received: by 2002:a05:6638:19c4:b0:32b:6436:f1c9 with SMTP id bi4-20020a05663819c400b0032b6436f1c9mr10301690jab.303.1652195090374; Tue, 10 May 2022 08:04:50 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id i11-20020a5e850b000000b0065a47e16f62sm4288988ioj.52.2022.05.10.08.04.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 08:04:50 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v6 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Tue, 10 May 2022 10:04:41 -0500 Message-Id: <20220510150441.20948-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510150441.20948-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510150441.20948-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-12.3 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, T_SCC_BODY_TEXT_LINE 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 Cc: Alexander Monakov Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Sender: "Libc-alpha" Unroll slightly and enforce good instruction scheduling. This improves performance on out-of-order machines. Note the unrolling allows for pipelined multiplies which helps a bit, but most of the gain is from enforcing better instruction scheduling for more ILP. 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 Co-authored-by: Alexander Monakov --- elf/dl-new-hash.h | 50 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 45 insertions(+), 5 deletions(-) diff --git a/elf/dl-new-hash.h b/elf/dl-new-hash.h index 40d88c81f9..cacbeec289 100644 --- a/elf/dl-new-hash.h +++ b/elf/dl-new-hash.h @@ -20,15 +20,55 @@ #define _DL_NEW_HASH_H 1 #include +/* For __glibc_unlikely. */ +#include static inline uint32_t __attribute__ ((unused)) -_dl_new_hash (const char *s) +_dl_new_hash (const char *signed_s) { - uint32_t h = 5381; - for (unsigned char c = *s; c != '\0'; c = *++s) - h = h * 33 + c; - return h; + const unsigned char *s = (const unsigned char *) signed_s; + unsigned int h = 5381; + unsigned int c0, c1; + for (;;) + { + c0 = (unsigned int) *s; + /* Unlikely length zero string so evens will be slightly less + common. */ + if (__glibc_unlikely (c0 == 0)) + { + return h; + } + + c1 = (unsigned int) *(s + 1); + if (c1 == 0) + { + c0 += h; + /* Ideal instruction scheduling is: + c0 += h; + h *= 32; + h += c0; + The asm statement ensures the compiler can't mess that up. */ + asm("" : "+r"(h) : "r"(c0)); + h = h * 32 + c0; + return h; + } + + /* Ideal instruction scheduling is: + c1 += c0; + h *= 33 * 33; + c0 *= 32; + c1 += c0; + h += c1; + The asm statements ensures the compiler can't mess that up. */ + c1 += c0; + asm("" : "+r"(c1), "+r"(c0)); + h *= 33 * 33; + c1 += c0 * 32; + asm("" : "+r"(c1)); + h += c1; + s += 2; + } }