From patchwork Thu Apr 14 14:55:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1617292 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=s95WSKzF; 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 (server2.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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KfMwN0Tjmz9sGZ for ; Fri, 15 Apr 2022 00:56:04 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 7E48C3858016 for ; Thu, 14 Apr 2022 14:56:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 7E48C3858016 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649948161; 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=s95WSKzFkbXK48QjMCAW8HFZ4zmrmvL5o9jGW7yEwaBUj6ZOk/aJSac8kxBHAu+E3 5KHScjyH5jS7GpUmHqnFL0vFqtStg9+WFc/SHwHkHcmrxpw8lMn81c+pQmfsuitqCv BeCyoGYy1jtP9wjb67CXGdGeIRIMPCYlyJsL4N/s= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x135.google.com (mail-il1-x135.google.com [IPv6:2607:f8b0:4864:20::135]) by sourceware.org (Postfix) with ESMTPS id 47E5B3858016 for ; Thu, 14 Apr 2022 14:55:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 47E5B3858016 Received: by mail-il1-x135.google.com with SMTP id d3so3241918ilr.10 for ; Thu, 14 Apr 2022 07:55: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=J4sEQHrShPaKJuxTrePMdayFSggo+GVOrwcVSe3S4uw=; b=gtqV9CfRMUA+v1Q4lcl0qBLd47xO8CF6mTZiZA+H+Ft+ccZfvFLK3vJifHbbzzYODo U7vTzdgPpsBQ7VqH2u19dOqvV7ytEs89jyODIGLivevdV+9jj8x9NbXfF2ZhoaVBsfHZ gOcDwyDi69gq0RijMZu8D9JeKYRYMk70jGVTR3/5OZqkjmmHrbm+dOY9uTdtMAh9b1H4 /Of0sLTONEkQvlxllVOFy0ACGo84ra5anSM6ajrr9dHUAj3CvYVfHmTFlbvmopFwD1uR jUTki2EQYdiCAIM71zPQP9eg7PUT8ObAU6qCK0Bi9/JUwf+R7U3EmHqZZspOYVbSlw6T XxvQ== X-Gm-Message-State: AOAM533nEGNSJwLs9C85h4r4DLEqPQf9iM7Mho66pIZvpp8z7Rh+Lv5H Uketxtg2clUGgV1RhLX2y03QptZoLs4= X-Google-Smtp-Source: ABdhPJxBncMJBMQPklB76ELGLh8C6J8bRcAe9FDksgKoaUuY8Qm5dqDJtmjlQmIm4lo4BJydCUnT6w== X-Received: by 2002:a92:6512:0:b0:2ca:1e16:5751 with SMTP id z18-20020a926512000000b002ca1e165751mr1317069ilb.210.1649948146400; Thu, 14 Apr 2022 07:55:46 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id i12-20020a926d0c000000b002c9db5fdf66sm1216629ilc.15.2022.04.14.07.55.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 07:55:46 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked Date: Thu, 14 Apr 2022 09:55:35 -0500 Message-Id: <20220414145540.194794-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=-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 | 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 Thu Apr 14 14:55: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: 1617293 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=SVq0teQ6; 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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KfMxB2VZtz9sGZ for ; Fri, 15 Apr 2022 00:56:46 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 63BAE3857359 for ; Thu, 14 Apr 2022 14:56:43 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 63BAE3857359 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649948203; bh=x2bwnuqyPpJp68CXfqEZzyUMHvFNeoP14B5UQrkaDhU=; 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=SVq0teQ6WZdUJ9zFXCOcD4ZcvFCD4V+6TtIsGvif+iFLag9Jq8LdQGEafIU4xqL1o ylPW0Ii5PPsoMiuDBhqOlv0saiAZOT0Ow+O3idseBmBC9h7iIDHbSUHuvHlgdXZ16w G3BRMhGKw9IydSzaCJW3m7VqT38bHenTecIrXEhI= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2f.google.com (mail-io1-xd2f.google.com [IPv6:2607:f8b0:4864:20::d2f]) by sourceware.org (Postfix) with ESMTPS id 4237B385803E for ; Thu, 14 Apr 2022 14:55:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4237B385803E Received: by mail-io1-xd2f.google.com with SMTP id x4so5629201iop.7 for ; Thu, 14 Apr 2022 07:55: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=x2bwnuqyPpJp68CXfqEZzyUMHvFNeoP14B5UQrkaDhU=; b=4vSokBW7YDXjlTH+6A8dzjDLBVOmnohVkmIf9tBws29+SkLF4f2Xm131RyVnEbfZxS 1PtxV1YPF8eZfIYHfOn6gTVYMfBSJIZnNCU84cZeglVL48NTQ9NHZRIj4IomtMb62PMZ tRkVFcKhNhNkysoD0VupKfYO+jBG+kn/AbyMwEl+mFcK43Pz+Si/OEG+92q903HMxq6Q 9Kjq5HixeaH8nsi6cErou+wIUOxDvrL8hTNEvbkbVwgvxBfrMnOSBxgTaleowfzAp73T sUkAtJWDi+fgk/F5Sv9MlLvdQKte63rm9xI4yuW4tgve1fq1cP9bRFiKsoQ8ChAGMM5q mbJg== X-Gm-Message-State: AOAM53315hmMJN47qt/glL801bOGZTG8qxWB9W9Qi8Ci96cchIbClBFG E63/fjrZ4YRAr2HHhFKaUqWO3rjNKLs= X-Google-Smtp-Source: ABdhPJzVDdeoKCFjmmFpxUcYUxlQpFTytcZ9aulH/upFM5F2BhboSuyq8mvbolozZPpWld7rsbwz3g== X-Received: by 2002:a05:6638:1a8b:b0:326:5eb7:d309 with SMTP id ce11-20020a0566381a8b00b003265eb7d309mr1425731jab.41.1649948147383; Thu, 14 Apr 2022 07:55:47 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id i12-20020a926d0c000000b002c9db5fdf66sm1216629ilc.15.2022.04.14.07.55.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 07:55:47 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 2/6] elf: Add tests for the dl hash funcs (_dl_new_hash and _dl_elf_hash) Date: Thu, 14 Apr 2022 09:55:36 -0500 Message-Id: <20220414145540.194794-2-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414145540.194794-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220414145540.194794-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 c96924e9c2..9c76673a40 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..dd1524abea --- /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(%lu), %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(%lu), %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 Thu Apr 14 14:55: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: 1617294 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=itNhmo6N; 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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KfMxz5nn9z9sG4 for ; Fri, 15 Apr 2022 00:57:27 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9DE103857350 for ; Thu, 14 Apr 2022 14:57:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9DE103857350 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649948245; bh=o1M+bfH9sSLiKv6gt/iLVrzinZ9WovJTWSt1Zi9ep5c=; 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=itNhmo6NxFXuAfyXDWHxJj+O8wR67sQulITtX8hjh3vxOwhXXNYFBR/KHxKF1EsPG wmSAUeHz7CuO2OYtMZyPoZ/55ZnWLHF+xwIJu4XzXTEZ8vTlv2OBDv/MTWja/Mes/B GNeiTlX0yWDIqmOKngoVlZYFeG8G6AUI51ITC6h8= 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 22FD03858016 for ; Thu, 14 Apr 2022 14:55:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 22FD03858016 Received: by mail-io1-xd2d.google.com with SMTP id 125so5622233iov.10 for ; Thu, 14 Apr 2022 07:55: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=o1M+bfH9sSLiKv6gt/iLVrzinZ9WovJTWSt1Zi9ep5c=; b=ouj5FuS1CrmqsQumYa2pq1vTlCi0IcvcaVKbBUOSDOAgfU+kw54pVm2B37WdkFaQsg /0Lk89u1SX9XM6Q2bbRTsZg3XWHyjiJz6fBM6nz6B+F93vmhpLQ4oP3ETSqkdhN/7wKu i/7JKkezvGPnPXC+Gzoqt5k4PU0Gbn8CrbYjxlz+96v5bXv4cAW+HSiKsJ+SmHjJlsmX rW+L7N8UC/NoYVb//Qolz1Bk1VkIMBvU3gPqs8GziMFkholguaSwmk+XxWSZjDCgTL7G 1SffwAp97Q9OewU4LkCeMuvjWn8ukgH07Mi6BO9pgU/xLR/x7/s7nxo77CLiBLzLZxXs rQZg== X-Gm-Message-State: AOAM530uml+1t7u7dmLdIgJrh7iiYGM+QD9t7gAiRtGTmQKGQgwAwp6N tmnqSrsACqCqX/Dt/yWPdYmqZerV/Rs= X-Google-Smtp-Source: ABdhPJy+Caah2BtC+pxSksCRPkh0+cAKxaqJQHXdoSzvG3RevQHgu2UAsVUiB2rnXBMFQE1hD4TJMg== X-Received: by 2002:a05:6638:40a7:b0:326:32c3:45b5 with SMTP id m39-20020a05663840a700b0032632c345b5mr1512140jam.181.1649948148319; Thu, 14 Apr 2022 07:55:48 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id i12-20020a926d0c000000b002c9db5fdf66sm1216629ilc.15.2022.04.14.07.55.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 07:55:48 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 3/6] nss: Add tests for the nss_hash in nss_hash.h Date: Thu, 14 Apr 2022 09:55:37 -0500 Message-Id: <20220414145540.194794-3-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414145540.194794-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220414145540.194794-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..9612eec909 --- /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) (%lu), %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 (%lu), %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 Thu Apr 14 14:55: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: 1617297 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=IDM0jE4q; 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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KfMzb46XKz9sG4 for ; Fri, 15 Apr 2022 00:58:51 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 669653857370 for ; Thu, 14 Apr 2022 14:58:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 669653857370 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649948329; 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=IDM0jE4qIEBQHjjUBu9hgDsicUG2I+WXRX9bay27BimcqFxOk/mLKOx5UwalRFZyd MWBzQ6z4jy5WX/Pjs3eENIXX/djA62vlwIyTrDVuTjEZ6rl3vb/LmpHRAao1vTciGa mSiYFtQUnBzQsEBjjNeaOFGXy2jwfySEtZeEwrwU= 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 330223857C50 for ; Thu, 14 Apr 2022 14:55:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 330223857C50 Received: by mail-io1-xd2a.google.com with SMTP id k25so5633208iok.8 for ; Thu, 14 Apr 2022 07:55: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=rsyFTAlf/PrGB4/sJpnkSREwk3Olkln2SNU2dJjOXTo=; b=nbhDV6osXBCgEigR4LEphFg/cgamb/xuO1esrSr8nIMG/rReX43HlWeJrUaNl3tSp6 UwtVfgrTYjYxhcvkDCznj7gg1FDBQyJ5vcW2SnCheMhmlCvfD0kgQahgVa5/thdebMDq 26T2Jzg+F5BKH/PLuNOeY3e89y5i2xzKfbR2iE/Uo3RDQ1Ah4CZbPhNPs7Ze17v0CT1K rjxS3q/c9/p58tgaVR+wNqFegFQc9RwoVHbCfP68QO62rQpdCdBpkwlhlq71ntyJsoh9 UhD+90dOxFY4uI1lqVBFb9rbHmjSP1E4qZbFYXdCHhcC+F5+OqJKn1i78+MZDUsfJgPN 4/vw== X-Gm-Message-State: AOAM5336zi5cUrzShdh8ZMsagBr3mAOmcb2dBUSz5h0yrna7tHCRlaWq Xr6FUBLMlQQTq7aeT5fVRqXsgZQQQYs= X-Google-Smtp-Source: ABdhPJzzB57u7aws1uqPUYUMZAlJ/GCmqFLlRbBND+trHwct7sFaL1tG1tvYvlBMEP8NyXEZjYpnCg== X-Received: by 2002:a05:6638:388e:b0:326:2adf:a365 with SMTP id b14-20020a056638388e00b003262adfa365mr1376437jav.7.1649948149245; Thu, 14 Apr 2022 07:55:49 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id i12-20020a926d0c000000b002c9db5fdf66sm1216629ilc.15.2022.04.14.07.55.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 07:55:49 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 4/6] benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash Date: Thu, 14 Apr 2022 09:55:38 -0500 Message-Id: <20220414145540.194794-4-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414145540.194794-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220414145540.194794-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 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 Thu Apr 14 14:55: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: 1617295 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=bYEPpR88; 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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KfMyn3S61z9sG4 for ; Fri, 15 Apr 2022 00:58:09 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 446773857363 for ; Thu, 14 Apr 2022 14:58:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 446773857363 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649948287; 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=bYEPpR88Tm6fPknwEkcxIhDls5JdlsjHfiOPHZNCJQinKxz5+Wd5unEoqS1PA+TI8 jqnk9aySBocR16+C7k4XjYvMVVPjfTyGJxOlWvaDxwtXyBCBuBK2nJT8rZ+NCc/ZMI q/17s4cUV9ZkOgrIEqBmVS9Eb6v5E2AU7h2Ni+Tg= 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 DD7843857350 for ; Thu, 14 Apr 2022 14:55:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org DD7843857350 Received: by mail-io1-xd32.google.com with SMTP id 125so5622340iov.10 for ; Thu, 14 Apr 2022 07:55: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=zj2NFHnTeLyhxkSHLGu3uAgkctu3K3V0M2ge6pbE41w=; b=3/YAhqNuH0p9sygYpAmX8JC+LHgKRdQcVPABLwsjraqGI+jFfOCVqhjwlw/o4QggTN 0QX9O6XukPT5PJaRZ5TjaqH9Ts3zvVFgm3G3ZG33ZWDRkZWfZ/+BsYp69X9FJLQaoH4c 60fK5hsj7shSjmg/1OdXouHPwM18FPF8h0k+MdDZpZffEAw2jCUqii9bdGoN+8wZ51cw rrxR3UoapYkfOy9MaXtEufa1GsIwmA2jVoEse/OyT9wrsxm/e3xsW4efGW7rRnQwGQZq eYMXytKnfKbAgsQe5t3Vsxb67nnwdpOW2WUx0wqPFGy+JUtsJu4Ply1tcFeu+HUmbuYT xjvQ== X-Gm-Message-State: AOAM530ZJvpw0YI4+DT9TgDNpdiXJHbLph9GFVLa3qFVHsN7KKuFaIqM 7AafoUJeDhU9e/dkxRzFiTlP0R5Zvt0= X-Google-Smtp-Source: ABdhPJw0z1kFKE0G6xPJKF1rgYIl1cgQ3XSQDOcdi6qifA8yuTw7AYNoAKph5YNuQAAtPK03O9s/bQ== X-Received: by 2002:a02:6a60:0:b0:315:4758:1be1 with SMTP id m32-20020a026a60000000b0031547581be1mr1398370jaf.316.1649948150057; Thu, 14 Apr 2022 07:55:50 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id i12-20020a926d0c000000b002c9db5fdf66sm1216629ilc.15.2022.04.14.07.55.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 07:55:49 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 5/6] nss: Optimize nss_hash in nss_hash.c Date: Thu, 14 Apr 2022 09:55:39 -0500 Message-Id: <20220414145540.194794-5-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414145540.194794-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220414145540.194794-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 Thu Apr 14 14:55: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: 1617298 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=jS0/fl7h; 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 (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KfN0W0MvBz9sG4 for ; Fri, 15 Apr 2022 00:59:39 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9D8223857363 for ; Thu, 14 Apr 2022 14:59:36 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9D8223857363 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1649948376; 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=jS0/fl7hSWj3TOoy+4zzwYHTnzrRwBwK6XXG0hGwE4QvtM2h8jka5rWIsaAeu646q VVncJq3mJQCmxPQtjdA070eTOrbp+wcaD+b9auVOROv1ELMPR+94W4x1YcdPwRKjH/ s2w1jPDmbcAAPTmflkj0MVvy+zyTd75Q17XRAWA0= 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 A992F3857362 for ; Thu, 14 Apr 2022 14:55:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A992F3857362 Received: by mail-io1-xd29.google.com with SMTP id x4so5629408iop.7 for ; Thu, 14 Apr 2022 07:55: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=ayvLBWaAmUglkXeAb9jA6PrIj3L3vSsibSoKqZXxkDY=; b=ovLXxxTY6e27epmedMC/tIXIDhKzUPza+/daLkf7WqlD3efX1CdTJfLHNDhUjNY/s/ x19luEHBs89BYgXwvQFjUWPT8o3ANeSOI4ZGJxjPpTuwfXyAkEHjCzJIrDOskYAfYikd wPly4UdbUevgJpPpzQHn+P2qOB/wsxfBi9KqZQY29c9QaZgC0MsdDlAB7iST2wyt+fND pL3GCKqnjbcb7denqeXcs67P2hbCxZtKGhEEXDowC+3g2aCljKMp0FNqXCJnsE94m+JV 2IkYT99TvXDYlnQ5i5yXFs5+1mFAr1l4pqeirpAQwuGvIRdbR+E05DTg1TxVAbBWL7S3 bv4g== X-Gm-Message-State: AOAM533PJ+jsROoVanyXGskUzB+PM927YG4A2ptstdUAw+N4egRWyJ0q pH6Ljbc+FuL6gKaPS/WEJ78MgmrJaAg= X-Google-Smtp-Source: ABdhPJw0my6DyVvIUhz9qf6gQxLIgDvXxEugiwc6E/sJ6QITlBnLT6Sy+xEn+26CphHC4wXBuAIwEg== X-Received: by 2002:a05:6638:25c2:b0:326:223d:4494 with SMTP id u2-20020a05663825c200b00326223d4494mr1351635jat.162.1649948150924; Thu, 14 Apr 2022 07:55:50 -0700 (PDT) Received: from localhost.localdomain (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.googlemail.com with ESMTPSA id i12-20020a926d0c000000b002c9db5fdf66sm1216629ilc.15.2022.04.14.07.55.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 07:55:50 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v2 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Thu, 14 Apr 2022 09:55:40 -0500 Message-Id: <20220414145540.194794-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20220414145540.194794-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220414145540.194794-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 Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.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; + } }