From patchwork Tue May 10 23:30:24 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629379 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=rXqK4TQr; 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 4KyZ6Q3Rdnz9sG2 for ; Wed, 11 May 2022 09:30:54 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E70FC3857815 for ; Tue, 10 May 2022 23:30:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E70FC3857815 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652225451; 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=rXqK4TQruo98qkIyBd+jSG0Q5G7mfym166pKC42f0bLg5GoO1leuIw7SMKlKWPYrM 0BCvuN9PsGRmx4nWeCS/yUpKybGsnH47LyR3coUux9w5FtHmjAv2T+vT3QEATNAE4S jbCCF7yU08hJw9W96iInIVo+4tOsFf4JJsHl2R50= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd33.google.com (mail-io1-xd33.google.com [IPv6:2607:f8b0:4864:20::d33]) by sourceware.org (Postfix) with ESMTPS id 616863858D33 for ; Tue, 10 May 2022 23:30:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 616863858D33 Received: by mail-io1-xd33.google.com with SMTP id f4so417354iov.2 for ; Tue, 10 May 2022 16:30:36 -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=KY4ym0R1GF9zQjrz1wmKAznLXdoFmGfZclTp7JXgQr0PnJEu/VyO3NQVjWesjynGfc Phuhq9H6GOC5MPAAgnEMIGGCqXv6sZ1II5dY9UH0QDahPcEGPvWRjShlYnfLpmt0qRkP jkYwJbveuv3MCOiPCoHcLRFf1k4dtI2W7tUCcftQY4z2eiBX5llGpOpHellVXhS52u7t 2Y4I/WQThXBsFfFq80W2D6K94qfaYctavclcW4eJa4qpcfhAh6SrPKkE06F5wZe6cgct CVyPqJTpQ6yunhXer44bpNIaFmUnJ6Gev7CsAyJdaDu1wVocmI6o103EK6Vj6vpCnKhI ND0g== X-Gm-Message-State: AOAM532jJ+IhOS6SvcyQrS0e46pq1JdqjM9ZKK+JQ+5otZPJcvHRMp7h mdKMwJ+01cTYP1rc+hDZn2B7cypCCoM= X-Google-Smtp-Source: ABdhPJwbJtJp+5aIDSsLI+2snWuAEyMHrPrfPf1S2AipmqKcpnVRXL5og4tCx0fKy7xYkIplweXfmQ== X-Received: by 2002:a05:6638:22c9:b0:32d:c4fb:a63c with SMTP id j9-20020a05663822c900b0032dc4fba63cmr2231952jat.253.1652225435478; Tue, 10 May 2022 16:30:35 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id x6-20020a056638026600b0032b3a7817bcsm159972jaq.128.2022.05.10.16.30.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 16:30:35 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v7 1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked Date: Tue, 10 May 2022 18:30:24 -0500 Message-Id: <20220510233029.637071-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 23:30:25 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629380 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=rkvdio4z; 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 4KyZ7C6vJlz9sG2 for ; Wed, 11 May 2022 09:31:35 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C614B385737A for ; Tue, 10 May 2022 23:31:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C614B385737A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652225493; 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=rkvdio4zwB7qY7aAvCpAp3lbJW+j+GnfzPVg4P0mClcxPspqwPERjwEaC8RKNrnTH FooqvJwlZ1kvNKB6fpCd0mbsoONQ1rI9bUyDRH2a1QIoh3UNLk5HstJBZtXLTL4UZy 1keYbkRqZpbA1Sde6xmK4HOdOWUHyxq7pRJHS1NM= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2b.google.com (mail-io1-xd2b.google.com [IPv6:2607:f8b0:4864:20::d2b]) by sourceware.org (Postfix) with ESMTPS id AB4E03858D3C for ; Tue, 10 May 2022 23:30:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org AB4E03858D3C Received: by mail-io1-xd2b.google.com with SMTP id f2so391233ioh.7 for ; Tue, 10 May 2022 16:30:37 -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=V4cj2VC71wT0o5XatYrXJnICwV46OBk1xayGmM4WcOINSO8cwzfmtqDiQgGUqySurN IsnDQZ9aOfT4z8HUHDe3RQQqNB5+8U58BD67ycGjlhg8ZofHzbsKefD8tYHgshMhwj1M n75Oad53s2s/80NvwTWwUylPmRx/7xFprzB4PpRVTr8tgc2f6/kjfrl5BuH7vgqpcmLK cVa2d+kgprwklx0SHbFBHDDWtO+i9M5TX8cAdI9+D0OYc6FXrUWa4mM/8l1KqARaqltP qBezaFzAeew1aqYFMCAhSU/Cqk0w3GroKmSOZa7TKtszBg+AhpjPV2PXUxi+TAnlB5uc G5aw== X-Gm-Message-State: AOAM531Kym3VAQV+PwR3Hb/Uzjzq/ohXgxjPQA0ZyuIypQECf8fDtjVk R6i4Lq85rYJG+13Pod7Q0E3Wrq9ojbA= X-Google-Smtp-Source: ABdhPJzpt+J72QwrgVNShwwcjWP+g08SyfdysfVUU96R5eBwEtWjv7IrRCSJ4RjceWCV+fNXwVcDKg== X-Received: by 2002:a05:6638:16cf:b0:32b:6ee7:8d7d with SMTP id g15-20020a05663816cf00b0032b6ee78d7dmr10904632jat.256.1652225436779; Tue, 10 May 2022 16:30:36 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id x6-20020a056638026600b0032b3a7817bcsm159972jaq.128.2022.05.10.16.30.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 16:30:36 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v7 2/6] elf: Add tests for the dl hash funcs (_dl_new_hash and _dl_elf_hash) Date: Tue, 10 May 2022 18:30:25 -0500 Message-Id: <20220510233029.637071-2-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510233029.637071-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510233029.637071-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 23:30:26 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629381 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=eQZsE+rp; 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 4KyZ813nDcz9sG2 for ; Wed, 11 May 2022 09:32:17 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5CDEC3856DC5 for ; Tue, 10 May 2022 23:32:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5CDEC3856DC5 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652225535; 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=eQZsE+rp9/27Cj9xkIF93LSPi45LK+idSJkuXwrVL1Yww840g54peTda7wEQekvS9 Pe3nTjUsGBznRuB3deXw0dgBD7F+ZgTZyMI3EfUyh0zjduk5MI1mQUo0yGH+nNaGXW xa1PJF/dviGaJmrUYr84njGX/I+2IxcUDzazOAIY= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd30.google.com (mail-io1-xd30.google.com [IPv6:2607:f8b0:4864:20::d30]) by sourceware.org (Postfix) with ESMTPS id C52CB3858D33 for ; Tue, 10 May 2022 23:30:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C52CB3858D33 Received: by mail-io1-xd30.google.com with SMTP id o190so384105iof.10 for ; Tue, 10 May 2022 16:30:38 -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=j4YqsHwkAzj0skiVlDRUbNDQ46CKGaC2uZ5t7zngYFZd4D8dmbm+dEw3OS4rp1RJg3 BG4YNn2Er0Axs6U/qLHnCB2jQ5eA3Tn4o/SBfQvgKSsR88bsOFkhbkQjwLaCe+tTa4iY KK71JvZU+nGuWHeO5Ezl3eMsXM6i4dRIJ7ZdzHPustd3vM5MZz1iPVL2KkGzd0Oi46RO mTKOoUgmxpFc5++iDmJGloRdyMOJuV+qgiJVw95BEU3PyT4GpvPw3Uh5U4Gra6VZTH7A oweD14vFBQMPDkHaML2eLsiDi0HxhEPgbpe87/ZT5h7j2mGjgHLTMUttShXlyVd/cWJ3 692Q== X-Gm-Message-State: AOAM531L178nBhvgnY/OB/zYtK8qMlR2lnxNECLU5Nk1gpl3hhYqrGsG wV9+3fnQdx/WNm50pjKsBYalO94DTZ0= X-Google-Smtp-Source: ABdhPJzCFvmSbzVzZMmIMe21O0xuzrc87Vf1cvAJZbUVfjQgBB+gCMXq+A/VLQXYNPVwR3EoeQqZUw== X-Received: by 2002:a05:6638:16d6:b0:32b:a283:a822 with SMTP id g22-20020a05663816d600b0032ba283a822mr11224812jat.145.1652225437914; Tue, 10 May 2022 16:30:37 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id x6-20020a056638026600b0032b3a7817bcsm159972jaq.128.2022.05.10.16.30.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 16:30:37 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v7 3/6] nss: Add tests for the nss_hash in nss_hash.h Date: Tue, 10 May 2022 18:30:26 -0500 Message-Id: <20220510233029.637071-3-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510233029.637071-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510233029.637071-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 23:30:27 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629382 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=q9Nt7qWE; 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 4KyZ8q0MLhz9sG2 for ; Wed, 11 May 2022 09:32:59 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E0C503856DCC for ; Tue, 10 May 2022 23:32:56 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E0C503856DCC DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652225576; 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=q9Nt7qWElM6HJ+CPfNtRjxWlyL6VNAWudYWcQzuFqNHcISPC6pvRdvCTou9zbcPVz Edlr1EolNtzfZ1rU4yTZcFNFn8kYbZgKOvJsPyX3HgrS6cuZ3NqUxiVo9XjxOhwWNN 6o9+0rycfrealV0tINbkHBhJX5XZwgdPkZFMvAGs= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd33.google.com (mail-io1-xd33.google.com [IPv6:2607:f8b0:4864:20::d33]) by sourceware.org (Postfix) with ESMTPS id 443EB3858C74 for ; Tue, 10 May 2022 23:30:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 443EB3858C74 Received: by mail-io1-xd33.google.com with SMTP id f4so417354iov.2 for ; Tue, 10 May 2022 16:30:39 -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=6dyGfRzRp5r3lL4UO6qRpNS70IVJhHexElzvnpYL3R58baFXnPM8dIzdlk5D78TeJ8 OzBm8D7k/y58nVRrJSSwXxIrn9f4JJsU5FAILvG1Mr/AEgAwsr97ry+UiGxET6MQbNXk bRSv/tvE9mhooIIkRorj56eAHg0FmNFy0dKVEXhUDAscUXbGzT4qopQhPxZa1B7+WuLx Zic12H+HW3aRfdIBwyWnqF9yiDPIeFjRSbr24qGKaJBlTX8VjUEX9YXRuw+rAJ69Q7Zw p+g2FNzZ+ZXGvR0MnhUUt5wr7hnpTDc20Oy1m6HXdEXWeYhfN9xfCSOGXPPmnX2oIUm7 37Mg== X-Gm-Message-State: AOAM5330ausn1Ks37JQbsfyFKwx6Aw7trAvV4xWuNGxr9yPWuesiNfq5 Eh83kZL2aZLGp4j4bhfmVnht1qQTCDI= X-Google-Smtp-Source: ABdhPJxicPf2oTQXrnQcsLO6CpEPZF/tdeIMUUHbQnOTmiLeFctQ4xYGzyjwE7BR4G9Tihr8vG6I2A== X-Received: by 2002:a02:84ac:0:b0:32b:a11b:4586 with SMTP id f41-20020a0284ac000000b0032ba11b4586mr10847456jai.231.1652225438755; Tue, 10 May 2022 16:30:38 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id x6-20020a056638026600b0032b3a7817bcsm159972jaq.128.2022.05.10.16.30.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 16:30:38 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v7 4/6] benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash Date: Tue, 10 May 2022 18:30:27 -0500 Message-Id: <20220510233029.637071-4-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510233029.637071-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510233029.637071-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 23:30:28 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629383 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=w8Zw/tIj; 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 4KyZ9f51YKz9sG2 for ; Wed, 11 May 2022 09:33:42 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 337263856247 for ; Tue, 10 May 2022 23:33:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 337263856247 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652225619; 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=w8Zw/tIjfLhKKXq2rGFEoxFknA21iWRpwzyukgKBdsFIC9AJdpU3xHXXg4y9ptUX6 ytGe7iZKqV9iG0wT61LE1BvWJ7mD8N2uxy7ahfk4ZbPNwknQ4DjWYLLKSwo2C949Yh Py33tW9n9aR5qL20/5RRUmAA2wk6Y4g2htdVHAKg= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2e.google.com (mail-io1-xd2e.google.com [IPv6:2607:f8b0:4864:20::d2e]) by sourceware.org (Postfix) with ESMTPS id 54FB73857815 for ; Tue, 10 May 2022 23:30:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 54FB73857815 Received: by mail-io1-xd2e.google.com with SMTP id h85so369175iof.12 for ; Tue, 10 May 2022 16:30:40 -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=jG9MNSFoCb4FGk9Q1O1+8lTkIRaZnT6Ipex3Hobazc7fH2TqqaVtrjgAIeC5e/YCT2 mZjk/sG4qzeojJmNJ4t2nWAOnFenUEl3fiVX9JGLU7nYJ3R2P3dzQ50SvwKh91JWSBE+ EuyCMClfEkbVRjKrVdocI5kDwUmntJ3EuI3MTwcVzkBcrzCwGag21C6y7D4DEGvDlR8B rUgRGuT6IrFktjRVnHBNpBHIdi84dw8Cm9oC4ttCg69pIl71OFycy5+S/AZbA6V3Ko8T BB87LSJ5gqyveRXYm/jisIOlQYwEk/1oiTl0OaUPtRD43J/9k46zj0MHOdIQw3Jp7fcU frug== X-Gm-Message-State: AOAM533uk5orum8rzCqRxSiRvPdHMX0LS1l2LTgFPwaR28mAbqUcdbXX F1kdGcMurI73OvwbDYj9+6MSa21/XcU= X-Google-Smtp-Source: ABdhPJzjSC2QFGYjF/uLXQiOCzQ4VjQRThYToRZ9sxN30srxEfXx+79rXsfor86bR7BfbXQvu9gLgQ== X-Received: by 2002:a02:a815:0:b0:32a:f654:47b8 with SMTP id f21-20020a02a815000000b0032af65447b8mr11673340jaj.129.1652225439392; Tue, 10 May 2022 16:30:39 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id x6-20020a056638026600b0032b3a7817bcsm159972jaq.128.2022.05.10.16.30.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 16:30:39 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v7 5/6] nss: Optimize nss_hash in nss_hash.c Date: Tue, 10 May 2022 18:30:28 -0500 Message-Id: <20220510233029.637071-5-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510233029.637071-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510233029.637071-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 23:30:29 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 1629384 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=eY4TuS05; 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 4KyZBW6Rvsz9sG6 for ; Wed, 11 May 2022 09:34:27 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BB5193856258 for ; Tue, 10 May 2022 23:34:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BB5193856258 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652225665; bh=GS1gok3gbtFzh4ET1bCn/qAZ7EOQZUVVfC6ZJNOyZao=; 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=eY4TuS05FttsnHeMmMrR0PI44GyTdTAaQewvT3mgzXQ46XTXtJVewbqEJYV5aIc7O 95qK8GhS73lA9KbIY0VhI57kZoPNZB1hmn019VEBIJdMrwyjV7nLZi/UVnd6xsHUov xI0tfRVpyxz7wTgC5QwDA/f2PE2LA7sRn+iJ8ahQ= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd36.google.com (mail-io1-xd36.google.com [IPv6:2607:f8b0:4864:20::d36]) by sourceware.org (Postfix) with ESMTPS id 637AA385735E for ; Tue, 10 May 2022 23:30:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 637AA385735E Received: by mail-io1-xd36.google.com with SMTP id r27so421734iot.1 for ; Tue, 10 May 2022 16:30:41 -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=GS1gok3gbtFzh4ET1bCn/qAZ7EOQZUVVfC6ZJNOyZao=; b=bPA9WVQJgFLUmlN1wgT53B3rSDoccZTD3UPAC+R7QTrZZNmO8DhcOLTUhlX9L6/R09 p0qaBdT4r8DkQRgpvGaOo/y9PLbfH+4MH+H+eEQSjMaDHgBsAKxv9rrQ3+/9oXuua7zQ 3C+N9rr18ZUIJZuolWnfku5o6VqaW9+4kcDA16xWWdtk+xgZLIbsfqF85lC5BKrQhI2h BL5m5hIyZyDH2sC5mYVRKGAUNyFjLViQo96cdHsjaCJk0cTPgpr1FvzaOddum40WZSTY 71P3jjejE+lnFBbtd6jmQfc5qEWBasShT1IdabDZ4ojMsHRDcxTCI5L+d66dA+ay8HqU UJqQ== X-Gm-Message-State: AOAM5302YWlLsc38wWqZ4zkN9kjSfNf++/Qxm717VrDNpFHU9Qi9yWvX nMWxiVc75ijKqSVmUpirTIVJuu19feI= X-Google-Smtp-Source: ABdhPJwF3g321c0L62zr2xK4epfa+eK1fBsrPSOOkPqn27SbfahlvQ+RqEKuSbAEO2k3nC7GwBcWyg== X-Received: by 2002:a6b:fd0a:0:b0:657:d01f:87a5 with SMTP id c10-20020a6bfd0a000000b00657d01f87a5mr9922262ioi.201.1652225440348; Tue, 10 May 2022 16:30:40 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id x6-20020a056638026600b0032b3a7817bcsm159972jaq.128.2022.05.10.16.30.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 May 2022 16:30:39 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v7 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Tue, 10 May 2022 18:30:29 -0500 Message-Id: <20220510233029.637071-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220510233029.637071-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220510233029.637071-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=30 runs Geometric of all benchmark New / Old: 0.674 type, length, New Time, Old Time, New Time / Old Time fixed, 0, 2.865, 2.72, 1.053 fixed, 1, 3.567, 2.489, 1.433 fixed, 2, 2.577, 3.649, 0.706 fixed, 3, 3.644, 5.983, 0.609 fixed, 4, 4.211, 6.833, 0.616 fixed, 5, 4.741, 9.372, 0.506 fixed, 6, 5.415, 9.561, 0.566 fixed, 7, 6.649, 10.789, 0.616 fixed, 8, 8.081, 11.808, 0.684 fixed, 9, 8.427, 12.935, 0.651 fixed, 10, 8.673, 14.134, 0.614 fixed, 11, 10.69, 15.408, 0.694 fixed, 12, 10.789, 16.982, 0.635 fixed, 13, 12.169, 18.411, 0.661 fixed, 14, 12.659, 19.914, 0.636 fixed, 15, 13.526, 21.541, 0.628 fixed, 16, 14.211, 23.088, 0.616 fixed, 32, 29.412, 52.722, 0.558 fixed, 64, 65.41, 142.351, 0.459 fixed, 128, 138.505, 295.625, 0.469 fixed, 256, 291.707, 601.983, 0.485 random, 2, 12.698, 12.849, 0.988 random, 4, 16.065, 15.857, 1.013 random, 8, 19.564, 21.105, 0.927 random, 16, 23.919, 26.823, 0.892 random, 32, 31.987, 39.591, 0.808 random, 64, 49.282, 71.487, 0.689 random, 128, 82.23, 145.364, 0.566 random, 256, 152.209, 298.434, 0.51 Co-authored-by: Alexander Monakov --- elf/dl-new-hash.h | 66 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 61 insertions(+), 5 deletions(-) diff --git a/elf/dl-new-hash.h b/elf/dl-new-hash.h index 40d88c81f9..c6d96a0452 100644 --- a/elf/dl-new-hash.h +++ b/elf/dl-new-hash.h @@ -20,15 +20,71 @@ #define _DL_NEW_HASH_H 1 #include +/* For __glibc_unlikely. */ +#include + +/* The simplest implementation of _dl_new_hash is: + +_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; +} + + We can get better performance, however, by slightly unrolling the + loop and explicitly specifying order of operations to prevent + reassosiation of instructions and ensure ideal scheduling. */ static inline uint32_t __attribute__ ((unused)) -_dl_new_hash (const char *s) +_dl_new_hash (const char *str) { - 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 *) str; + 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 statements are to prevent reassosiation that would result in + more instruction interdependencies and worse scheduling. */ + 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 are to prevent reassosiation that would result in + more instruction interdependencies and worse scheduling. */ + c1 += c0; + asm("" : "+r"(c1), "+r"(c0)); + h *= 33 * 33; + c1 += c0 * 32; + asm("" : "+r"(c1)); + h += c1; + s += 2; + } }