Author: hselasky
Date: Sun Feb 18 12:54:21 2018
New Revision: 329519
URL: https://svnweb.freebsd.org/changeset/base/329519
Log:
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.
MFC after: 1 week
Sponsored by: Mellanox Technologies
Modified:
head/sys/compat/linuxkpi/common/include/linux/radix-tree.h
head/sys/compat/linuxkpi/common/src/linux_radix.c
Modified: head/sys/compat/linuxkpi/common/include/linux/radix-tree.h
==============================================================================
--- head/sys/compat/linuxkpi/common/include/linux/radix-tree.h Sun Feb 18
11:36:46 2018 (r329518)
+++ head/sys/compat/linuxkpi/common/include/linux/radix-tree.h Sun Feb 18
12:54:21 2018 (r329519)
@@ -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 <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];
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: head/sys/compat/linuxkpi/common/src/linux_radix.c
==============================================================================
--- head/sys/compat/linuxkpi/common/src/linux_radix.c Sun Feb 18 11:36:46
2018 (r329518)
+++ head/sys/compat/linuxkpi/common/src/linux_radix.c Sun Feb 18 12:54:21
2018 (r329519)
@@ -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,44 @@ 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;
+ if ((index & mask) == 0)
+ goto restart;
+ } else {
+ node = next;
+ height--;
+ }
+ } while (height != -1);
+ iter->index = index;
+ return (true);
}
void *
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
