From patchwork Wed May 18 17:26:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 54169 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9060A3856DEA for ; Wed, 18 May 2022 17:27:02 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9060A3856DEA DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652894822; bh=dOkEpRuQslrJ4pwRMx+eIHaWHag3oMyt+D/qGVhvRuQ=; 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=AUyj4HD920+m2RjZaXJapIFYIgB1vopfzK+u90mAvzjOS9tTcz8zchNd7U0PTH8Bu hyVx8s8w0vFJPCg+QdLhWRJ0ADmMLs3KW3UW48rqgUs2OdYfWOqgc0otL8TMSMPlGB JPdEorVrC1+TcUukuLlB8fLWDPn8HBqJHXKRFF9k= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x136.google.com (mail-il1-x136.google.com [IPv6:2607:f8b0:4864:20::136]) by sourceware.org (Postfix) with ESMTPS id 807673858C2C for ; Wed, 18 May 2022 17:26:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 807673858C2C Received: by mail-il1-x136.google.com with SMTP id 3so2000438ily.2 for ; Wed, 18 May 2022 10:26: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=dOkEpRuQslrJ4pwRMx+eIHaWHag3oMyt+D/qGVhvRuQ=; b=aolViIwSvIt0j9pQXV8CLHJt+/Tf8FqCpzoWeaDVTHAtZPYRbS7Odw7WrchU5MHBlh zB/QuTno2wNzSylupLsqLipmyS/Oyjs+OKgQ1+qNvBSqJDlpsG9xmwkjf+t0WMc6HUzh lobwmi5lNnV9x2xMqRPeFpf4KKqS7ghP5+jUP6q3icm/tZKE8RPCBqkF8GXM/biA+dhv ELIpRjOWOMCSTsBCAi2h/ipMysT4HuPsUkcuYviNZFIHnfASlgD/t+3UNjlWaFV9S60Q nnDdEc3MPewHdLAZTXIJyPJPloaMGfWRQhSkjN01uowsnGYxMDjcInxrhIBmGytqTO4e ez/g== X-Gm-Message-State: AOAM533QFiYoVwRts+lUnJK0cLXjQYOTAM68OieMDWJDzoVXbNb8hKUY G3PA+oNcOTMUKetvYwvJmaNGvealPqo= X-Google-Smtp-Source: ABdhPJxiGTsEwitZZih27Rjb32oQj6CQqWvy720zqmUUd4GDU6ldJnVxdFviTaiJrsIl80vIFKkhbg== X-Received: by 2002:a05:6e02:2146:b0:2d1:28ae:ef04 with SMTP id d6-20020a056e02214600b002d128aeef04mr425565ilv.160.1652894800667; Wed, 18 May 2022 10:26:40 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id r2-20020a02b102000000b0032b3a78179fsm18598jah.99.2022.05.18.10.26.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 18 May 2022 10:26:40 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v10 1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked Date: Wed, 18 May 2022 12:26:30 -0500 Message-Id: <20220518172635.291119-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" No change to the code other than moving the function to dl-new-hash.h. Changed name so its now in the reserved namespace. Reviewed-by: Siddhesh Poyarekar --- elf/dl-lookup.c | 13 ++----------- elf/dl-new-hash.h | 40 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 42 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..8641bb4196 --- /dev/null +++ b/elf/dl-new-hash.h @@ -0,0 +1,40 @@ +/* _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 +/* For __always_inline. */ +#include + +static __always_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; +} + +/* For testing/benchmarking purposes. */ +#define __simple_dl_new_hash _dl_new_hash + + +#endif /* dl-new-hash.h */ From patchwork Wed May 18 17:26:31 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 54170 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 876FD385734A for ; Wed, 18 May 2022 17:27:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 876FD385734A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652894864; bh=1RB1f/sc7ciFSDiAcHwVA9ScT5CB5kCl4yr2asRkkac=; 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=ujS1gAafW2QvA3/VwF8NmtYbN54yhktnmTkI576XJuPSoBgOxkb/lkD98+K0JEjDV Jg/wamkok+ExXo7g2noB4Gfh95adEM6LGCyQJ0SUxfUK+HJX2Lc4sXRKw+5YUlYipL xbDj42n2tT0gTN/NAvfDVh0fGIeQyiFbKv8AxBD0= 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 CF1193858D33 for ; Wed, 18 May 2022 17:26:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CF1193858D33 Received: by mail-io1-xd36.google.com with SMTP id q203so3107493iod.0 for ; Wed, 18 May 2022 10:26:42 -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=1RB1f/sc7ciFSDiAcHwVA9ScT5CB5kCl4yr2asRkkac=; b=evKDqDJwNBZlHKvuqa8J+O6anU4bsj4sbIcdKerzeQ54u+sB5skTXNHVwSd/W7JM6b qYgDZPchXQZ9Sxa/tWcC9Hlp50NeRz3AAutHsV4zL09c1vZm80BqFy5ZpXP91oCZM7wB A1/zTUk3elZlvmEBKQ6iKEOiHWZ8HFZw2RpvdS4FLUELj6zDUKP2XZIcSYI3U9nPdENc irG3BLc8Rk/exU8PhBvSl6t5Z5QbSeZlP38dVuW2gn2+Xq8XryBgJhMKRh1k2cQlhZPg SCcJRa17mZxypTjcWDN0CYywdZb3pY/j0YngN0XDGNi+sTZBNyvYA4uWKg5b1TPGPDDL MwJQ== X-Gm-Message-State: AOAM5327oebEfXQlKnvo/QxrBk/PNfSMO2tcTsqSpqEr8wxiTU2pDL78 DtmCF8wyDckGbZ0Ddvytzreis7qLfZA= X-Google-Smtp-Source: ABdhPJxNLQ6gJWjFBz76WzVWXBAguiFzwlZQudwj1Bu6uWYnzp6xNsXjufJ4xB/xlu9AwJ1GET/TWw== X-Received: by 2002:a05:6638:d13:b0:32b:cf94:275b with SMTP id q19-20020a0566380d1300b0032bcf94275bmr378641jaj.22.1652894801995; Wed, 18 May 2022 10:26:41 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id r2-20020a02b102000000b0032b3a78179fsm18598jah.99.2022.05.18.10.26.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 18 May 2022 10:26:41 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v10 2/6] elf: Add tests for the dl hash funcs (_dl_new_hash and _dl_elf_hash) Date: Wed, 18 May 2022 12:26:31 -0500 Message-Id: <20220518172635.291119-2-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220518172635.291119-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220518172635.291119-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" If we want to further optimize the functions tests are needed. Reviewed-by: Siddhesh Poyarekar --- elf/Makefile | 1 + elf/simple-dl-hash.h | 42 ++++++++++++++++ elf/tst-dl-hash.c | 115 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 158 insertions(+) create mode 100644 elf/simple-dl-hash.h create mode 100644 elf/tst-dl-hash.c diff --git a/elf/Makefile b/elf/Makefile index ce3345ed92..adf1bcf6ce 100644 --- a/elf/Makefile +++ b/elf/Makefile @@ -312,6 +312,7 @@ tests := \ tst-array4 \ tst-array5 \ tst-auxv \ + tst-dl-hash \ tst-leaks1 \ tst-stringtable \ tst-tls9 \ diff --git a/elf/simple-dl-hash.h b/elf/simple-dl-hash.h new file mode 100644 index 0000000000..53702b3c55 --- /dev/null +++ b/elf/simple-dl-hash.h @@ -0,0 +1,42 @@ +/* __simple_dl_elf_hash for testing true 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 _SIMPLE_DL_ELF_HASH_H +#define _SIMPLE_DL_ELF_HASH_H 1 + +#include + +/* For testing/benchmarking purposes. Real implementation in + sysdeps/generic/dl-hash.h. */ +static uint32_t +__attribute__ ((unused)) +__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; +} + +#endif /* simple-dl-hash.h */ diff --git a/elf/tst-dl-hash.c b/elf/tst-dl-hash.c new file mode 100644 index 0000000000..8697eb73a0 --- /dev/null +++ b/elf/tst-dl-hash.c @@ -0,0 +1,115 @@ +/* Test dl-hash functions. + 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 +#include +#include +#include +#include +#include +#include +#include + +typedef unsigned int (*hash_f) (const char *); + + + +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) + FAIL_EXIT1 ("FAIL: random %s(%zu), %x != %x\n", name, len, expec, res); + + 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 Wed May 18 17:26:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 54171 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 570B33858025 for ; Wed, 18 May 2022 17:28:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 570B33858025 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652894906; bh=IlP377vkGfDJz97lj2ZXisxM22IRGQLxg3xkwKA4urQ=; 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=gadmmf2mJeBjN3xw8lx80lKdnf3LBdiev7xPD0JFtZ+nYGEOc846BXPrKuJncVHcc 1aRkfWXBU6n5xf4wT8XiRhP2SP7Op0OpPGJpopxZmE+TPiKb2veErVCTmjEP2LdzIs +vJoV0D/I0lpNVIExoev1O/RjELkI0CYVEx6nAeA= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-io1-xd2c.google.com (mail-io1-xd2c.google.com [IPv6:2607:f8b0:4864:20::d2c]) by sourceware.org (Postfix) with ESMTPS id D517A3858025 for ; Wed, 18 May 2022 17:26:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D517A3858025 Received: by mail-io1-xd2c.google.com with SMTP id m6so3054490iob.4 for ; Wed, 18 May 2022 10:26:43 -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=IlP377vkGfDJz97lj2ZXisxM22IRGQLxg3xkwKA4urQ=; b=SxxW/cKWowYkqN9Ux1CdfAgJahD7lgTAcrFTqSCOXYWNkOS5dEPSJXUSLeTzh11XcV iwiGIfchSBDvrqhIu+6mBdn2jwbgCVmKF5eV2HHDTKMfIBuzn+WzAMTf4GPIhd+hKsSv 2oYCjCZpkZ+orFQ/gjueT9Nou87HZBmSQmYunR+2TSbsqKXbezQgqKrH2gh8gPcXoh2n eaohxX4gzx5u8VqDgWd8E7wgAjiyC60ob1XhnckQEwJmNnDb/lSeDbu1XJGk5DfeaYFJ vJjfFY9LbwZpPP0UeXXl3Xa3k3ikq4Al0AVmZD/dRFkZjYckRK+22nXfRBgTAwLm35AZ dsYA== X-Gm-Message-State: AOAM53153sHqZ9CaSbr+SkWrGNMkp5KF3DAeeZhW7xVRtjhZ1tTPdG0B HCEmmTUmLq2rH8/rWB/lEQyhGXivzCQ= X-Google-Smtp-Source: ABdhPJzMoSvhdip06tMh9rOW5a3dIga3SyHhNhJxuiy6+4NtOqnRpXNKuk0zV325c9SE/f5Cq/bkjw== X-Received: by 2002:a05:6638:3e9a:b0:32d:b131:8dbd with SMTP id ch26-20020a0566383e9a00b0032db1318dbdmr298993jab.265.1652894803005; Wed, 18 May 2022 10:26:43 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id r2-20020a02b102000000b0032b3a78179fsm18598jah.99.2022.05.18.10.26.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 18 May 2022 10:26:42 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v10 3/6] nss: Add tests for the nss_hash in nss_hash.h Date: Wed, 18 May 2022 12:26:32 -0500 Message-Id: <20220518172635.291119-3-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220518172635.291119-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220518172635.291119-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" If we want to further optimize the function tests are needed. Reviewed-by: Siddhesh Poyarekar --- nss/Makefile | 1 + nss/nss_hash.c | 16 +++++++++ nss/simple-nss-hash.h | 42 +++++++++++++++++++++++ nss/tst-nss-hash.c | 80 +++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 139 insertions(+) create mode 100644 nss/simple-nss-hash.h 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/nss_hash.c b/nss/nss_hash.c index 27a348ea9b..f9e17d068a 100644 --- a/nss/nss_hash.c +++ b/nss/nss_hash.c @@ -75,4 +75,20 @@ __nss_hash (const void *keyarg, size_t len) return h; } +/* For testing/benchmarking purposes. */ +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; +} + + libc_hidden_def (__nss_hash) diff --git a/nss/simple-nss-hash.h b/nss/simple-nss-hash.h new file mode 100644 index 0000000000..47708972e7 --- /dev/null +++ b/nss/simple-nss-hash.h @@ -0,0 +1,42 @@ +/* __simple_nss_hash for testing nss_hash function + 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 _SIMPLE_NSS_HASH_H +#define _SIMPLE_NSS_HASH_H 1 + +#include + +/* For testing/benchmarking purposes. Real implementation in + nss/nss_hash.c. */ +static uint32_t +__attribute__ ((unused)) +__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; +} + + +#endif /* simple-nss-hash.h */ diff --git a/nss/tst-nss-hash.c b/nss/tst-nss-hash.c new file mode 100644 index 0000000000..5ec1f9b0c5 --- /dev/null +++ b/nss/tst-nss-hash.c @@ -0,0 +1,80 @@ +/* Test __nss_hash + 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 +#include +#include +#include +#include +#include +#include + +uint32_t __nss_hash (const void *__key, size_t __length); + +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) + FAIL_EXIT1 ("FAIL: random (%zu), %x != %x\n", len, expec, res); + + 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 Wed May 18 17:26:33 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 54173 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BB1393856DC7 for ; Wed, 18 May 2022 17:29:55 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BB1393856DC7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652894995; bh=E2OB9sxDb8URAslJE1PNqacdy1lb1WQl2gA8Llm7lns=; 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=wL6aYf7uovt1qljiCphuDgxOuaFPypYAyZg+RNjUk+PR5Dn4ZagGhH0VXe9AfQd5d JndnGoVoEV+3INZOyN7HX/h/zugArS2iPDq5IF32MPLzkNArCsJL1KkBhNLiVzwceG 4mkS7TI9m1A24+Ui6PqfnwXOE385P8bfQnpt4RFw= 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 0046A385734A for ; Wed, 18 May 2022 17:26:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0046A385734A Received: by mail-il1-x135.google.com with SMTP id s6so1967496ilp.9 for ; Wed, 18 May 2022 10:26:44 -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=E2OB9sxDb8URAslJE1PNqacdy1lb1WQl2gA8Llm7lns=; b=u6UBIKB59+M01UiAvVmAGIL873hJZqyzZWD60YoBoz8szJKr/3oub83z6Le6Nzvu5A hIl1zFT78bncOL1YVXXmfQFH6vCzsnvjfkhO2sHuXKCSWUbP4c/mQCCBM7VHtxC5fP9t aww/e59Qv7GUVGb+2x3rO3dotCwGAWN13G/kKU/JXVhSGeWdgY0bTo99ySb/+0vTPOKK KTt/Mmv0eebChcvul/PGL3BrMp85HZRwXc6vDd9XXbY158vKAXKbeW993WQ9syjk0nVp c6in/3xd2GCCGrUlAZ1TqBroizyx7nF3bIVmt0TSyAqmtG5Uhv/7D/DGVJv7HnZ9ennW jZiQ== X-Gm-Message-State: AOAM532i63aunv3w9Almqhsg0Por696lCu/7V4UfinVEGMwC4HxVwoSi N419sKtGgf6/6W9EZZX6X0+Zgw+nfj0= X-Google-Smtp-Source: ABdhPJzQBtIP9rCvC7VdDBjFCYzjmW5MOLHIiBVwPTsEEMm4xgrNTjwUO1gRAksGXk0ZUhP9AUluDA== X-Received: by 2002:a92:7c11:0:b0:2ca:36df:e2f2 with SMTP id x17-20020a927c11000000b002ca36dfe2f2mr416517ilc.149.1652894803947; Wed, 18 May 2022 10:26:43 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id r2-20020a02b102000000b0032b3a78179fsm18598jah.99.2022.05.18.10.26.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 18 May 2022 10:26:43 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v10 4/6] benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash Date: Wed, 18 May 2022 12:26:33 -0500 Message-Id: <20220518172635.291119-4-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220518172635.291119-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220518172635.291119-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Benchtests are for throughput and include random / fixed size benchmarks. --- benchtests/Makefile | 25 ++++- benchtests/README | 9 +- benchtests/bench-dl-elf-hash.c | 27 +++++ benchtests/bench-dl-new-hash.c | 25 +++++ benchtests/bench-hash-funcs-kernel.h | 92 ++++++++++++++++ benchtests/bench-hash-funcs.c | 152 +++++++++++++++++++++++++++ benchtests/bench-nss-hash.c | 26 +++++ 7 files changed, 348 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-kernel.h 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..067de9fca4 --- /dev/null +++ b/benchtests/bench-dl-elf-hash.c @@ -0,0 +1,27 @@ +/* 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 +#include +#define TEST_FUNC(x, y) _dl_elf_hash (x) +#define SIMPLE_TEST_FUNC(x, y) __simple_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..3c8a1d5a82 --- /dev/null +++ b/benchtests/bench-dl-new-hash.c @@ -0,0 +1,25 @@ +/* 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 SIMPLE_TEST_FUNC(x, y) __simple_dl_new_hash (x) + +#define TEST_NAME "_dl_new_hash" + +#include "bench-hash-funcs.c" diff --git a/benchtests/bench-hash-funcs-kernel.h b/benchtests/bench-hash-funcs-kernel.h new file mode 100644 index 0000000000..9f9f245641 --- /dev/null +++ b/benchtests/bench-hash-funcs-kernel.h @@ -0,0 +1,92 @@ +/* Actual benchmark kernels used by bench-hash-funcs.h + 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 + . */ + + + +/* We go through the trouble of using macros here because many of the + hash functions are meant to be inlined so its not fair to benchmark + them with a function pointer where they won't be inlinable. */ +#undef RUN_FUNC +#undef POSTFIX +#ifdef SIMPLE +# define RUN_FUNC SIMPLE_TEST_FUNC +# define POSTFIX _simple +#else +# define RUN_FUNC TEST_FUNC +# define POSTFIX _optimized +#endif + +#define PRIMITIVE_CAT(x, y) x ## y +#define CAT(x, y) PRIMITIVE_CAT (x, y) + +static double __attribute__ ((noinline, noclone)) +CAT (do_one_test_kernel, POSTFIX) (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 (RUN_FUNC (s, len)); + } + + TIMING_NOW (start); + for (iters = NFIXED_ITERS; iters; --iters) + { + DO_NOT_OPTIMIZE_OUT (RUN_FUNC (s, len)); + } + TIMING_NOW (stop); + + TIMING_DIFF (cur, start, stop); + + (void) (len); + return (double) cur / (double) NFIXED_ITERS; +} + +static double __attribute__ ((noinline, noclone)) +CAT (do_rand_test_kernel, POSTFIX) (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 (RUN_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 (RUN_FUNC (bufs + offset, sizes[i])); + } + } + TIMING_NOW (stop); + + TIMING_DIFF (cur, start, stop); + + (void) (sizes); + return (double) cur / (double) (NRAND_ITERS * NRAND_BUFS); +} diff --git a/benchtests/bench-hash-funcs.c b/benchtests/bench-hash-funcs.c new file mode 100644 index 0000000000..3d3c736ffc --- /dev/null +++ b/benchtests/bench-hash-funcs.c @@ -0,0 +1,152 @@ +/* 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 SIMPLE_TEST_FUNC +# error "No SIMPLE_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 = 128 +}; + +#include "bench-hash-funcs-kernel.h" +#define SIMPLE +#include "bench-hash-funcs-kernel.h" + +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_simple", do_one_test_kernel_simple (buf, len)); + json_attr_double (json_ctx, "time_optimized", do_one_test_kernel_optimized (buf, len)); + + json_element_object_end (json_ctx); +} + +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_simple", + do_rand_test_kernel_simple (bufs, sizes)); + json_attr_double (json_ctx, "time_optimized", + do_rand_test_kernel_optimized (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..7e369428a2 --- /dev/null +++ b/benchtests/bench-nss-hash.c @@ -0,0 +1,26 @@ +/* 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 +#include +#define TEST_FUNC __nss_hash +#define SIMPLE_TEST_FUNC __simple_nss_hash + +uint32_t __nss_hash (const void *__key, size_t __length); + +#include "bench-hash-funcs.c" From patchwork Wed May 18 17:26:34 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Noah Goldstein X-Patchwork-Id: 54172 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2A7853856DC5 for ; Wed, 18 May 2022 17:29:13 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2A7853856DC5 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652894953; bh=kCaK88SxrRZGN8OM6+L3uZIO7mcP3fV2eiWX4EuZI8c=; 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=NN4Zcd2TqgYQlAaKUfNvQezlkWag+5tnzYeFlY6RgZMviZA+/x1eEerHTX8SEIh7g hpI1L8Dh80LcZCQtQCxecqNsXC7eGiLHtCiDAGmoJbpTdLAJNG/sSaKYnxSrSqwX+p K7sOSPsE4wFq37I5gCFXtHjROjhHhiOrgnuhmv2w= 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 C7BE63856DC5 for ; Wed, 18 May 2022 17:26:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C7BE63856DC5 Received: by mail-io1-xd2e.google.com with SMTP id y12so3037430ior.7 for ; Wed, 18 May 2022 10:26:45 -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=kCaK88SxrRZGN8OM6+L3uZIO7mcP3fV2eiWX4EuZI8c=; b=VQOHGFbBxgKJzTxN96mPDWc+Zk5a3NCabBGLp5FFsCA+vDJlQ0kGPwjGZ9nuCp4Mr7 g73IISVx95+7vUFEjeT+T1k2lNmkZLcKW4TZImt2u5ipk82YMyjwzUMtS0uTFqZIfXJ7 /Tp6+4GLNxXQbN35lPXIPPu3PBZKBm/S58nVeVsZgdiV1Ulg4GYfVyB4UiV3j8G7viol C71q6sdVBnkDxryzvNXLLheTCmm/jCkNpRegVdmDu8WV9mNorYKKvOKDnaGm9YrMmfMl 29cWI2/lNUysw2ChSjzzYoqFSXivRUFUUFKnnu9NN8jtTJ6Vu62aw3puBHvauCFrNUe1 MJlA== X-Gm-Message-State: AOAM5337GNKIrk2ZmmUXeGQfNPEOoBHTSUsFGRFjAQMmjbbRwGsi3h3S 8rf8DzgepgTBiYe7NzoPfJOv7LRwOI4= X-Google-Smtp-Source: ABdhPJwH9737AesEzkcrksVVWizq5DA6+WCLGk8yVM1Hx9ifV27E8EjUbh2vGGIF4RHyum/yBreVgQ== X-Received: by 2002:a05:6638:160d:b0:32b:d9d2:f2f2 with SMTP id x13-20020a056638160d00b0032bd9d2f2f2mr346609jas.68.1652894804879; Wed, 18 May 2022 10:26:44 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id r2-20020a02b102000000b0032b3a78179fsm18598jah.99.2022.05.18.10.26.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 18 May 2022 10:26:44 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v10 5/6] nss: Optimize nss_hash in nss_hash.c Date: Wed, 18 May 2022 12:26:34 -0500 Message-Id: <20220518172635.291119-5-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220518172635.291119-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220518172635.291119-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Noah Goldstein via Libc-alpha From: Noah Goldstein Reply-To: Noah Goldstein Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" The prior unrolling didn't really do much as it left the dependency chain between iterations. Unrolled the loop for 4 so 4x multiplies could be pipelined in out-of-order machines. Results for __nss_hash Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz Time as Geometric Mean of N=25 runs Geometric of all benchmark New / Old: 0.845 type, length, New Time, Old Time, New Time / Old Time fixed, 0, 4.019, 3.729, 1.078 fixed, 1, 4.95, 5.707, 0.867 fixed, 2, 5.152, 5.657, 0.911 fixed, 3, 4.641, 5.721, 0.811 fixed, 4, 5.551, 5.81, 0.955 fixed, 5, 6.525, 6.552, 0.996 fixed, 6, 6.711, 6.561, 1.023 fixed, 7, 6.715, 6.767, 0.992 fixed, 8, 7.874, 7.915, 0.995 fixed, 9, 8.888, 9.767, 0.91 fixed, 10, 8.959, 9.762, 0.918 fixed, 11, 9.188, 9.987, 0.92 fixed, 12, 9.708, 10.618, 0.914 fixed, 13, 10.393, 11.14, 0.933 fixed, 14, 10.628, 12.097, 0.879 fixed, 15, 10.982, 12.965, 0.847 fixed, 16, 11.851, 14.429, 0.821 fixed, 32, 24.334, 34.414, 0.707 fixed, 64, 55.618, 86.688, 0.642 fixed, 128, 118.261, 224.36, 0.527 fixed, 256, 256.183, 538.629, 0.476 random, 2, 11.194, 11.556, 0.969 random, 4, 17.516, 17.205, 1.018 random, 8, 23.501, 20.985, 1.12 random, 16, 28.131, 29.212, 0.963 random, 32, 35.436, 38.662, 0.917 random, 64, 45.74, 58.868, 0.777 random, 128, 75.394, 121.963, 0.618 random, 256, 139.524, 260.726, 0.535 --- nss/nss_hash.c | 92 ++++++++++++++++++++++---------------------------- 1 file changed, 41 insertions(+), 51 deletions(-) diff --git a/nss/nss_hash.c b/nss/nss_hash.c index f9e17d068a..1d3787e675 100644 --- a/nss/nss_hash.c +++ b/nss/nss_hash.c @@ -19,74 +19,64 @@ /* 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); - } - } - return h; -} + 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 */ + } -/* For testing/benchmarking purposes. */ -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; + 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 Wed May 18 17:26: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: 54174 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DE4463856DF9 for ; Wed, 18 May 2022 17:30:37 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DE4463856DF9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1652895037; bh=8Vs97fYDawrUaO792KB6O9J4G5gIJKscwLs7SL6jpVU=; 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=JanUjCyQQQVvGP/pngBx4sbuDRr+GIb84X/uYa5cB5bJ54VWAxJqlTpYiR7pnnjM5 WyyLvQVEd1umyhnKDfcAcwendMD2WmDX4L9lNT9E1vmypTHfT/tjLbDEwTD8PsJ/yr OHsa8wg5xxCGiHPhzdH9x79TJ1CBqUMYUQ325fQ4= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-il1-x136.google.com (mail-il1-x136.google.com [IPv6:2607:f8b0:4864:20::136]) by sourceware.org (Postfix) with ESMTPS id 6D5803856DCB for ; Wed, 18 May 2022 17:26:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6D5803856DCB Received: by mail-il1-x136.google.com with SMTP id 3so2000438ily.2 for ; Wed, 18 May 2022 10:26:46 -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=8Vs97fYDawrUaO792KB6O9J4G5gIJKscwLs7SL6jpVU=; b=67BIzmeXTwt3x5chb56/Cn4EudouLlkNPrL32zdB1Mpg3BxTD5jvozyT1lxu8KAd/T VDHf59FUxuyK5q/25OQEwGazUQmM1W01Uk3vfGxm5A/3EOqQdsBstDyocSTGzn4KS/t2 5jXp4/IqQgwDGZGfBBVnyUGaF8UtFRUVTbOqlvt9tqXXBkdBXumVK8xonrYIlHTnGV2H SMqsWUVIjobQ2bD9ZwwFSiM7gllIvNVYoRXgzPAJjmm6j7FVGuhbOWiNjkdg5NfKCp8Y dP23Ynn/p1htsWTlvAiVm0lEL0p01N6w+sTVX2tUx5JCm1KfWpmPNAQHeQfFKMQFhB6f FKbw== X-Gm-Message-State: AOAM530UtYnBwfzfCRLbODOoCh9G9xrtkfUTGXYPKcJvWtmDpQwjzuWu nC+bYaqsTtqCSk17eyfH3OvLeBpg2cY= X-Google-Smtp-Source: ABdhPJxams1HzMQniN4bRkX55fSL47Oqpql7JBL56vFfW2iHCicI/Idpr2SI07nnwEh8gRvrqoSltA== X-Received: by 2002:a92:d708:0:b0:2d0:ecd5:894c with SMTP id m8-20020a92d708000000b002d0ecd5894cmr386498iln.201.1652894805878; Wed, 18 May 2022 10:26:45 -0700 (PDT) Received: from noah-tgl.. (node-17-161.flex.volo.net. [76.191.17.161]) by smtp.gmail.com with ESMTPSA id r2-20020a02b102000000b0032b3a78179fsm18598jah.99.2022.05.18.10.26.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 18 May 2022 10:26:45 -0700 (PDT) To: libc-alpha@sourceware.org Subject: [PATCH v10 6/6] elf: Optimize _dl_new_hash in dl-new-hash.h Date: Wed, 18 May 2022 12:26:35 -0500 Message-Id: <20220518172635.291119-6-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220518172635.291119-1-goldstein.w.n@gmail.com> References: <20220414041231.926415-1-goldstein.w.n@gmail.com> <20220518172635.291119-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.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Unroll slightly and enforce good instruction scheduling. This improves performance on out-of-order machines. The unrolling allows for pipelined multiplies. As well, as an optional sysdep, reorder the operations and prevent reassosiation for better scheduling and higher ILP. This commit only adds the barrier for x86, although it should be either no change or a win for any architecture. 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 --- benchtests/bench-dl-new-hash.c | 3 +- elf/{dl-new-hash.h => simple-dl-new-hash.h} | 20 ++-- elf/tst-dl-hash.c | 1 + sysdeps/generic/dl-new-hash.h | 111 ++++++++++++++++++++ sysdeps/x86/dl-new-hash.h | 24 +++++ 5 files changed, 146 insertions(+), 13 deletions(-) rename elf/{dl-new-hash.h => simple-dl-new-hash.h} (75%) create mode 100644 sysdeps/generic/dl-new-hash.h create mode 100644 sysdeps/x86/dl-new-hash.h diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c index 3c8a1d5a82..040fa7ce01 100644 --- a/benchtests/bench-dl-new-hash.c +++ b/benchtests/bench-dl-new-hash.c @@ -16,7 +16,8 @@ License along with the GNU C Library; if not, see . */ -#include +#include +#include #define TEST_FUNC(x, y) _dl_new_hash (x) #define SIMPLE_TEST_FUNC(x, y) __simple_dl_new_hash (x) diff --git a/elf/dl-new-hash.h b/elf/simple-dl-new-hash.h similarity index 75% rename from elf/dl-new-hash.h rename to elf/simple-dl-new-hash.h index 8641bb4196..1437b1bd36 100644 --- a/elf/dl-new-hash.h +++ b/elf/simple-dl-new-hash.h @@ -1,4 +1,4 @@ -/* _dl_new_hash for elf symbol lookup +/* __simple_dl_new_hash for testing true elf symbol lookup. Copyright (C) 2022 Free Software Foundation, Inc. This file is part of the GNU C Library. @@ -16,16 +16,16 @@ License along with the GNU C Library; if not, see . */ -#ifndef _DL_NEW_HASH_H -#define _DL_NEW_HASH_H 1 +#ifndef _SIMPLE_DL_NEW_HASH_H +#define _SIMPLE_DL_NEW_HASH_H 1 #include -/* For __always_inline. */ -#include -static __always_inline uint32_t +/* For testing/benchmarking purposes. Real implementation in + sysdeps/generic/dl-new-hash.h. */ +static uint32_t __attribute__ ((unused)) -_dl_new_hash (const char *s) +__simple_dl_new_hash (const char *s) { uint32_t h = 5381; for (unsigned char c = *s; c != '\0'; c = *++s) @@ -33,8 +33,4 @@ _dl_new_hash (const char *s) return h; } -/* For testing/benchmarking purposes. */ -#define __simple_dl_new_hash _dl_new_hash - - -#endif /* dl-new-hash.h */ +#endif /* simple-dl-new-hash.h */ diff --git a/elf/tst-dl-hash.c b/elf/tst-dl-hash.c index 8697eb73a0..b21766c63d 100644 --- a/elf/tst-dl-hash.c +++ b/elf/tst-dl-hash.c @@ -18,6 +18,7 @@ #include +#include #include #include #include diff --git a/sysdeps/generic/dl-new-hash.h b/sysdeps/generic/dl-new-hash.h new file mode 100644 index 0000000000..1faf309c97 --- /dev/null +++ b/sysdeps/generic/dl-new-hash.h @@ -0,0 +1,111 @@ +/* _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 +/* For __always_inline. */ +#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 by slightly unrolling the loop to + pipeline the multiples, which gcc cannot easily do due to + dependencies across iterations. + + As well, as an architecture specific option we add asm statements + to explicitly specify order of operations and prevent reassociation + of instructions that lengthens the loop carried dependency. This + may have no affect as the compiler may have ordered instructions + the same way without it but in testing this has not been the case + for GCC. Improving GCC to reliably schedule instructions ideally + cannot be easily done. + + Architecture(s) that use the reassociation barries are: + x86 + + Note it is very unlikely the reassociation barriers would + de-optimize performance on any architecture and with an imperfect + compiler it may help performance, especially on out-of-order cpus, + so it is suggested that the respective maintainers add them. + + architecture maintainers are encouraged to benchmark this with + __asm_reassociation_barrier defined to __asm__ like it is in x86. +*/ + + +#ifndef __asm_reassociation_barrier +# define __asm_reassociation_barrier(...) +#endif + +static __always_inline uint32_t +__attribute__ ((unused)) +_dl_new_hash (const char *str) +{ + const unsigned char *s = (const unsigned char *) str; + unsigned int h = 5381; + unsigned int c0, c1; + for (;;) + { + c0 = s[0]; + /* Since hashed string is normally not empty, this is unlikely on the + first iteration of the loop. */ + if (__glibc_unlikely (c0 == 0)) + return h; + + c1 = s[1]; + if (c1 == 0) + { + /* Ideal computational order is: + c0 += h; + h *= 32; + h += c0; */ + c0 += h; + __asm_reassociation_barrier("" : "+r"(h) : "r"(c0)); + h = h * 32 + c0; + return h; + } + + /* Ideal computational order is: + c1 += c0; + h *= 33 * 33; + c0 *= 32; + c1 += c0; + h += c1; */ + c1 += c0; + __asm_reassociation_barrier("" : "+r"(c1), "+r"(c0)); + h *= 33 * 33; + c1 += c0 * 32; + __asm_reassociation_barrier("" : "+r"(c1)); + h += c1; + s += 2; + } +} + +#endif /* dl-new-hash.h */ diff --git a/sysdeps/x86/dl-new-hash.h b/sysdeps/x86/dl-new-hash.h new file mode 100644 index 0000000000..ce8fb5a838 --- /dev/null +++ b/sysdeps/x86/dl-new-hash.h @@ -0,0 +1,24 @@ +/* _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 + . */ + +#ifdef __asm_reassociation_barrier +# error "__asm_reassociation_barrier should never already be defined." +#endif + +#define __asm_reassociation_barrier __asm__ +#include