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

2 files changed, 66 insertions, 8 deletions

diff --git a/sys/compat/linuxkpi/common/include/linux/radix-tree.h b/sys/compat/linuxkpi/common/include/linux/radix-tree.h
index 0edf04e..cd7c56cb 100644
--- a/sys/compat/linuxkpi/common/include/linux/radix-tree.h
+++ b/sys/compat/linuxkpi/common/include/linux/radix-tree.h
@@ -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,10 +34,14 @@
 #include <linux/types.h>
 
 #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];
@@ -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_ */
diff --git a/sys/compat/linuxkpi/common/src/linux_radix.c b/sys/compat/linuxkpi/common/src/linux_radix.c
index 6a8bd11..053f08b 100644
--- a/sys/compat/linuxkpi/common/src/linux_radix.c
+++ b/sys/compat/linuxkpi/common/src/linux_radix.c
@@ -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
@@ -76,6 +76,45 @@ 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 *
 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
 {