From nobody Wed Jun 01 21:51:45 2022 X-Original-To: dev-commits-src-branches@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id BA0CC1B5CB84; Wed, 1 Jun 2022 21:51:45 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4LD2ss4bpHz4rML; Wed, 1 Jun 2022 21:51:45 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1654120305; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=AXOrMKV7FgMeleZhYs5ZePBdUvqVOPpFt6TG4HuN99g=; b=lhm1KqaFyp6fUBWhn4WJ1e0yxU2vUxsFpHNIK00gIloHCvkObRen2zD/4tnXjMRX3nqQU6 SVw1bz0L6KVoW7aqRA+a7Bqg36gnHlnjkKlWmMxdm7voHAIjC4Um/nRGZUBCrev5djO1va 9NWlwRwVPzxI90uPT73d9eUymjh5DoomDtXXKM8X1/YdnBaEin+DS7kzUtKrkrOyCanc1P jRwMmIWiCcA2h9vfa2ZtG4hkUnCaL05BODY5QMmomT5ovagM8h94fpsAhiJCMOSnOEBwQ/ D+rEGag+k9XQUZ2ntRol5rfOhIobkcVdlTgiO/sWtPDKtr2/egLNgtQNKVPWvA== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 7361B1A9; Wed, 1 Jun 2022 21:51:45 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 251Lpjca042727; Wed, 1 Jun 2022 21:51:45 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 251LpjJ5042726; Wed, 1 Jun 2022 21:51:45 GMT (envelope-from git) Date: Wed, 1 Jun 2022 21:51:45 GMT Message-Id: <202206012151.251LpjJ5042726@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Vladimir Kondratyev Subject: git: 2f382e4469ca - stable/13 - LinuxKPI: Implement linux/hashtable.h for FreeBSD. List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: wulf X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 2f382e4469cad95f2710ef2642cd757167b77a7f Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1654120305; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=AXOrMKV7FgMeleZhYs5ZePBdUvqVOPpFt6TG4HuN99g=; b=HiRzAuIHTPR2xbg++Nfm/btAeoG4WdAir6Fvj+8Wfcuoa5hW+NHRwQie44GuCPJCzfztWw 4+YILiAGTPZ4VsSloqfKuJiGod2wHilTA0Sf4taxGnQhYGj/eC7dTUkHC3GVrgHtdDYGIb BSOvbic5I9EoySIDVZHqChvcGU/Mt4GvxwguyuVbrmFDE49Q5isZLJOjGUQ2VNYbVAq72K KTJlI9I0xYhLOjZtvj8sIdInAHcOzvWDdiYrUHM9Nxfo0CxxWBVxrvTKLTwGNo557cr2AV hMG2BRClylBU+5KBkQpsXS2euwDEu1qS2MekP5er0CVbOewKsCKq9khBRNe7qQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1654120305; a=rsa-sha256; cv=none; b=OC5X5/vU0GQ1MuZkMXPrML7w9qGv4ly+UI9zhFlGrZEn3kgLhKdxrWIq5crElAVHK0sPw8 ORgi7eQz2iyKnQ7q1ObjvczmB71+45m8ERC48LXllvb2D6yFmYSrTB1UBz1NpPsYcdS3b0 n2JGL2e1V1KOsHZbC0EjL2FR+ie/MlgGXO0dhbIYqgMsX4C6brRGU8PshWSqlje71+bUNq hTHVxyXJgq9v3cEqUGTPcuqGWDwNSiziXeX+W82HGl4FHRAElS7q8p/Ub0ZPwukYCct23F T0NXE0thmcp2SzR6A8Trpfs7N0m99Nw/SgBtqLxEGzPqjc88HT7Mo5ogDRs+6Q== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch stable/13 has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=2f382e4469cad95f2710ef2642cd757167b77a7f commit 2f382e4469cad95f2710ef2642cd757167b77a7f Author: Hans Petter Selasky AuthorDate: 2022-05-10 12:16:20 +0000 Commit: Vladimir Kondratyev CommitDate: 2022-06-01 21:50:13 +0000 LinuxKPI: Implement linux/hashtable.h for FreeBSD. This implementation uses the concurrency kit, CK, API directly which is suitable for use with EPOCH(9) and RCU under FreeBSD. No functional change intended. The initial "linux/hash.h" code was obtained from DragonFlyBSD via FreeBSD's drm-kmod in ports. Differential Revision: https://reviews.freebsd.org/D35162 Reviewed by: bz@ and markj@ MFC after: 1 week Sponsored by: NVIDIA Networking (cherry picked from commit f9e90c24737f96ab97ad534d925fe37a7f0a6f58) --- sys/compat/linuxkpi/common/include/linux/hash.h | 76 +++++++++ .../linuxkpi/common/include/linux/hashtable.h | 187 +++++++++++++++++++++ 2 files changed, 263 insertions(+) diff --git a/sys/compat/linuxkpi/common/include/linux/hash.h b/sys/compat/linuxkpi/common/include/linux/hash.h new file mode 100644 index 000000000000..c75814c96724 --- /dev/null +++ b/sys/compat/linuxkpi/common/include/linux/hash.h @@ -0,0 +1,76 @@ +/* + * SPDX-License-Identifier: BSD-2-Clause + * + * Copyright (c) 2022 NVIDIA corporation & affiliates. + * Copyright (c) 2013 François Tigeot + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice unmodified, this list of conditions, and the following + * disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _LINUXKPI_LINUX_HASH_H_ +#define _LINUXKPI_LINUX_HASH_H_ + +#include +#include +#include + +#include + +#include + +static inline u64 +hash_64(u64 val, u8 bits) +{ + u64 ret; + u8 x; + + ret = bits; + + for (x = 0; x != sizeof(ret); x++) { + u64 chunk = (val >> (8 * x)) & 0xFF; + ret = HASHSTEP(ret, chunk); + } + return (ret >> (64 - bits)); +} + +static inline u32 +hash_32(u32 val, u8 bits) +{ + u32 ret; + u8 x; + + ret = bits; + + for (x = 0; x != sizeof(ret); x++) { + u32 chunk = (val >> (8 * x)) & 0xFF; + ret = HASHSTEP(ret, chunk); + } + return (ret >> (32 - bits)); +} + +#if BITS_PER_LONG == 64 +#define hash_long(...) hash_64(__VA_ARGS__) +#else +#define hash_long(...) hash_32(__VA_ARGS__) +#endif + +#endif /* _LINUXKPI_LINUX_HASH_H_ */ diff --git a/sys/compat/linuxkpi/common/include/linux/hashtable.h b/sys/compat/linuxkpi/common/include/linux/hashtable.h new file mode 100644 index 000000000000..a7a30143a58e --- /dev/null +++ b/sys/compat/linuxkpi/common/include/linux/hashtable.h @@ -0,0 +1,187 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause + * + * Copyright (c) 2022 NVIDIA corporation & affiliates. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice unmodified, this list of conditions, and the following + * disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#ifndef _LINUXKPI_LINUX_HASHTABLE_H +#define _LINUXKPI_LINUX_HASHTABLE_H + +#include +#include + +#include +#include +#include +#include +#include +#include + +#include + +struct lkpi_hash_entry { + CK_LIST_ENTRY(lkpi_hash_entry) entry; +}; + +struct lkpi_hash_head { + CK_LIST_HEAD(, lkpi_hash_entry) head; +}; + +#define DEFINE_HASHTABLE(name, bits) \ + struct lkpi_hash_head name[1UL << (bits)] + +#define DEFINE_READ_MOSTLY_HASHTABLE(name, bits) \ + struct lkpi_hash_head name[1UL << (bits)] __read_mostly + +#define DECLARE_HASHTABLE(name, bits) \ + struct lkpi_hash_head name[1UL << (bits)] + +#define HASH_SIZE(name) ARRAY_SIZE(name) +#define HASH_BITS(name) ilog2(HASH_SIZE(name)) + +#define hash_min(...) \ + hash_long(__VA_ARGS__) + +static inline void +__hash_init(struct lkpi_hash_head *ht, unsigned long size) +{ + unsigned long x; + + for (x = 0; x != size; x++) + CK_LIST_INIT(&ht[x].head); +} + +#define hash_init(ht) \ + __hash_init(ht, HASH_SIZE(ht)) + +#define hash_add(...) \ + hash_add_rcu(__VA_ARGS__) + +static inline void +__hash_node_type_assert(struct hlist_node *node) +{ + /* + * Unfortunately Linux doesn't have an own type for the hash + * table node entries. The purpose of this function is simply + * to check the type of the passed argument. + */ + CTASSERT(sizeof(struct lkpi_hash_entry) == sizeof(*node)); +} + +#define hash_add_rcu(ht, node, key) do { \ + struct lkpi_hash_head *__head = &(ht)[hash_min(key, HASH_BITS(ht))]; \ + __hash_node_type_assert(node); \ + KASSERT(((struct lkpi_hash_entry *)(node))->entry.cle_prev == NULL, \ + ("node is already on list or was not zeroed")); \ + CK_LIST_INSERT_HEAD(&__head->head, \ + (struct lkpi_hash_entry *)(node), entry); \ +} while (0) + +static inline bool +hash_hashed(struct hlist_node *node) +{ + return (((struct lkpi_hash_entry *)node)->entry.cle_prev != NULL); +} + +static inline bool +__hash_empty(struct lkpi_hash_head *ht, unsigned long size) +{ + unsigned long x; + + for (x = 0; x != size; x++) { + if (!CK_LIST_EMPTY(&ht[x].head)) + return (false); + } + return (true); +} + +#define hash_empty(ht) \ + __hash_empty(ht, HASH_SIZE(ht)) + +#define hash_del(...) \ + hash_del_rcu(__VA_ARGS__) + +static inline void +hash_del_rcu(struct hlist_node *node) +{ + CK_LIST_REMOVE((struct lkpi_hash_entry *)node, entry); + memset(node, 0, sizeof(*node)); +} + +#define __hash_first(ht, type, member) ({ \ + const struct lkpi_hash_entry *__first = CK_LIST_FIRST(&(ht)->head); \ + __hash_node_type_assert(&((type *)0)->member); \ + (__first != NULL ? container_of((const void *)__first, type, member) : NULL); \ +}) + +#define __hash_next(obj, type, member) ({ \ + const struct lkpi_hash_entry *__next = \ + CK_LIST_NEXT((struct lkpi_hash_entry *)&(obj)->member, entry); \ + __hash_node_type_assert(&(obj)->member); \ + (__next != NULL ? container_of((const void *)__next, type, member) : NULL); \ +}) + +#define hash_for_each(...) \ + hash_for_each_rcu(__VA_ARGS__) + +#define hash_for_each_rcu(name, bkt, obj, member) \ + for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \ + (bkt) != HASH_SIZE(name); (bkt)++) \ + for ((obj) = __hash_first(&(name)[bkt], \ + __typeof(*(obj)), member); \ + (obj) != NULL; \ + (obj) = __hash_next(obj, \ + __typeof(*(obj)), member)) + +#define hash_for_each_safe(name, bkt, tmp, obj, member) \ + for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \ + (bkt) != HASH_SIZE(name); (bkt)++) \ + for ((obj) = __hash_first(&(name)[bkt], \ + __typeof(*(obj)), member); \ + (obj) != NULL && ((tmp) = &__hash_next(obj, \ + __typeof(*(obj)), member)->member, 1); \ + (obj) = container_of(tmp, __typeof(*(obj)), member)) + +#define hash_for_each_possible(...) \ + hash_for_each_possible_rcu(__VA_ARGS__) + +#define hash_for_each_possible_rcu_notrace(...) \ + hash_for_each_possible_rcu(__VA_ARGS__) + +#define hash_for_each_possible_rcu(name, obj, member, key) \ + for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \ + __typeof(*(obj)), member); \ + (obj) != NULL; \ + (obj) = __hash_next(obj, __typeof(*(obj)), member)) + +#define hash_for_each_possible_safe(name, obj, tmp, member, key) \ + for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \ + __typeof(*(obj)), member); \ + (obj) != NULL && ((tmp) = &__hash_next(obj, \ + __typeof(*(obj)), member)->member, 1); \ + (obj) = container_of(tmp, __typeof(*(obj)), member)) + +#endif /* _LINUXKPI_LINUX_HASHTABLE_H */