From owner-svn-src-stable-11@freebsd.org Sun Feb 25 10:37:07 2018 Return-Path: Delivered-To: svn-src-stable-11@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id C3976F27BA7; Sun, 25 Feb 2018 10:37:07 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 6EE66765F6; Sun, 25 Feb 2018 10:37:07 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 69C653CD3; Sun, 25 Feb 2018 10:37:07 +0000 (UTC) (envelope-from hselasky@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w1PAb7gr018506; Sun, 25 Feb 2018 10:37:07 GMT (envelope-from hselasky@FreeBSD.org) Received: (from hselasky@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w1PAb7Be018504; Sun, 25 Feb 2018 10:37:07 GMT (envelope-from hselasky@FreeBSD.org) Message-Id: <201802251037.w1PAb7Be018504@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: hselasky set sender to hselasky@FreeBSD.org using -f From: Hans Petter Selasky Date: Sun, 25 Feb 2018 10:37:07 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-11@freebsd.org Subject: svn commit: r329973 - in stable/11/sys/compat/linuxkpi/common: include/linux src X-SVN-Group: stable-11 X-SVN-Commit-Author: hselasky X-SVN-Commit-Paths: in stable/11/sys/compat/linuxkpi/common: include/linux src X-SVN-Commit-Revision: 329973 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-stable-11@freebsd.org X-Mailman-Version: 2.1.25 Precedence: list List-Id: SVN commit messages for only the 11-stable src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 25 Feb 2018 10:37:08 -0000 Author: hselasky Date: Sun Feb 25 10:37:07 2018 New Revision: 329973 URL: https://svnweb.freebsd.org/changeset/base/329973 Log: MFC r329519: Implement support for radix_tree_for_each_slot() and radix_tree_exception() in the LinuxKPI and use unsigned long type for the radix tree index. Sponsored by: Mellanox Technologies Modified: stable/11/sys/compat/linuxkpi/common/include/linux/radix-tree.h stable/11/sys/compat/linuxkpi/common/src/linux_radix.c Directory Properties: stable/11/ (props changed) Modified: stable/11/sys/compat/linuxkpi/common/include/linux/radix-tree.h ============================================================================== --- stable/11/sys/compat/linuxkpi/common/include/linux/radix-tree.h Sun Feb 25 10:35:28 2018 (r329972) +++ stable/11/sys/compat/linuxkpi/common/include/linux/radix-tree.h Sun Feb 25 10:37:07 2018 (r329973) @@ -2,7 +2,7 @@ * Copyright (c) 2010 Isilon Systems, Inc. * Copyright (c) 2010 iX Systems, Inc. * Copyright (c) 2010 Panasas, Inc. - * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. + * Copyright (c) 2013-2018 Mellanox Technologies, Ltd. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -34,11 +34,15 @@ #include #define RADIX_TREE_MAP_SHIFT 6 -#define RADIX_TREE_MAP_SIZE (1 << RADIX_TREE_MAP_SHIFT) -#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE - 1) -#define RADIX_TREE_MAX_HEIGHT \ - DIV_ROUND_UP((sizeof(long) * NBBY), RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE - 1UL) +#define RADIX_TREE_MAX_HEIGHT \ + howmany(sizeof(long) * NBBY, RADIX_TREE_MAP_SHIFT) +#define RADIX_TREE_ENTRY_MASK 3UL +#define RADIX_TREE_EXCEPTIONAL_ENTRY 2UL +#define RADIX_TREE_EXCEPTIONAL_SHIFT 2 + struct radix_tree_node { void *slots[RADIX_TREE_MAP_SIZE]; int count; @@ -50,6 +54,10 @@ struct radix_tree_root { int height; }; +struct radix_tree_iter { + unsigned long index; +}; + #define RADIX_TREE_INIT(mask) \ { .rnode = NULL, .gfp_mask = mask, .height = 0 }; #define INIT_RADIX_TREE(root, mask) \ @@ -57,8 +65,19 @@ struct radix_tree_root { #define RADIX_TREE(name, mask) \ struct radix_tree_root name = RADIX_TREE_INIT(mask) +#define radix_tree_for_each_slot(slot, root, iter, start) \ + for ((iter)->index = (start); \ + radix_tree_iter_find(root, iter, &(slot)); (iter)->index++) + +static inline int +radix_tree_exception(void *arg) +{ + return ((uintptr_t)arg & RADIX_TREE_ENTRY_MASK); +} + void *radix_tree_lookup(struct radix_tree_root *, unsigned long); void *radix_tree_delete(struct radix_tree_root *, unsigned long); int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); +bool radix_tree_iter_find(struct radix_tree_root *, struct radix_tree_iter *, void ***); #endif /* _LINUX_RADIX_TREE_H_ */ Modified: stable/11/sys/compat/linuxkpi/common/src/linux_radix.c ============================================================================== --- stable/11/sys/compat/linuxkpi/common/src/linux_radix.c Sun Feb 25 10:35:28 2018 (r329972) +++ stable/11/sys/compat/linuxkpi/common/src/linux_radix.c Sun Feb 25 10:37:07 2018 (r329973) @@ -2,7 +2,7 @@ * Copyright (c) 2010 Isilon Systems, Inc. * Copyright (c) 2010 iX Systems, Inc. * Copyright (c) 2010 Panasas, Inc. - * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. + * Copyright (c) 2013-2018 Mellanox Technologies, Ltd. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -43,10 +43,10 @@ __FBSDID("$FreeBSD$"); static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat"); -static inline int +static inline unsigned long radix_max(struct radix_tree_root *root) { - return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1; + return ((1UL << (root->height * RADIX_TREE_MAP_SHIFT)) - 1UL); } static inline int @@ -74,6 +74,45 @@ radix_tree_lookup(struct radix_tree_root *root, unsign out: return (item); +} + +bool +radix_tree_iter_find(struct radix_tree_root *root, struct radix_tree_iter *iter, + void ***pppslot) +{ + struct radix_tree_node *node; + unsigned long index = iter->index; + int height; + +restart: + node = root->rnode; + if (node == NULL) + return (false); + height = root->height - 1; + if (height == -1 || index > radix_max(root)) + return (false); + do { + unsigned long mask = RADIX_TREE_MAP_MASK << (RADIX_TREE_MAP_SHIFT * height); + unsigned long step = 1UL << (RADIX_TREE_MAP_SHIFT * height); + int pos = radix_pos(index, height); + struct radix_tree_node *next; + + /* track last slot */ + *pppslot = node->slots + pos; + + next = node->slots[pos]; + if (next == NULL) { + index += step; + index &= -step; + if ((index & mask) == 0) + goto restart; + } else { + node = next; + height--; + } + } while (height != -1); + iter->index = index; + return (true); } void *