Page MenuHomeFreeBSD
Files F144038080

D54809.1771013862.diff
No OneTemporary
Actions

Size
8 KB
Referenced Files
None
Subscribers
None

D54809.1771013862.diff
View Options

diff --git a/sys/compat/linuxkpi/common/include/linux/radix-tree.h b/sys/compat/linuxkpi/common/include/linux/radix-tree.h
--- a/sys/compat/linuxkpi/common/include/linux/radix-tree.h
+++ b/sys/compat/linuxkpi/common/include/linux/radix-tree.h
@@ -38,12 +38,19 @@
#define RADIX_TREE_MAX_HEIGHT \
howmany(sizeof(long) * NBBY, RADIX_TREE_MAP_SHIFT)
+#define RADIX_TREE_MAX_TAGS 3
+#define RADIX_TREE_TAG_LONGS RADIX_TREE_MAP_SIZE
+
#define RADIX_TREE_ENTRY_MASK 3UL
#define RADIX_TREE_EXCEPTIONAL_ENTRY 2UL
#define RADIX_TREE_EXCEPTIONAL_SHIFT 2
+#define RADIX_TREE_ITER_TAG_MASK 0x0f
+#define RADIX_TREE_ITER_TAGGED 0x10
+
struct radix_tree_node {
void *slots[RADIX_TREE_MAP_SIZE];
+ unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
int count;
};
@@ -51,6 +58,8 @@
struct radix_tree_node *rnode;
gfp_t gfp_mask;
int height;
+ /* Linux stores root tags inside `gfp_mask`. */
+ unsigned long tags[RADIX_TREE_MAX_TAGS];
};
struct radix_tree_iter {
@@ -64,9 +73,16 @@
#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++)
+#define radix_tree_for_each_slot(slot, root, iter, start) \
+ for ((iter)->index = (start); \
+ radix_tree_iter_find(root, iter, &(slot), 0); \
+ (iter)->index++)
+
+#define radix_tree_for_each_slot_tagged(slot, root, iter, start, tag) \
+ for ((iter)->index = (start); \
+ radix_tree_iter_find(root, iter, &(slot), \
+ RADIX_TREE_ITER_TAGGED | tag); \
+ (iter)->index++)
static inline void *
radix_tree_deref_slot(void **slot)
@@ -84,7 +100,12 @@
void *radix_tree_delete(struct radix_tree_root *, unsigned long);
int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
int radix_tree_store(struct radix_tree_root *, unsigned long, void **);
-bool radix_tree_iter_find(const struct radix_tree_root *, struct radix_tree_iter *, void ***);
+bool radix_tree_iter_find(const struct radix_tree_root *, struct radix_tree_iter *, void ***, int);
void radix_tree_iter_delete(struct radix_tree_root *, struct radix_tree_iter *, void **);
+void *radix_tree_tag_set(struct radix_tree_root *root, unsigned long index, unsigned int tag);
+void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, unsigned int tag);
+int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag);
+unsigned int radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items);
+unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag);
#endif /* _LINUXKPI_LINUX_RADIX_TREE_H_ */
diff --git a/sys/compat/linuxkpi/common/src/linux_radix.c b/sys/compat/linuxkpi/common/src/linux_radix.c
--- a/sys/compat/linuxkpi/common/src/linux_radix.c
+++ b/sys/compat/linuxkpi/common/src/linux_radix.c
@@ -52,6 +52,81 @@
return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
}
+static inline int
+root_tag_get(const struct radix_tree_root *root, unsigned tag)
+{
+ return (test_bit(tag, root->tags));
+}
+
+static inline void
+root_tag_set(struct radix_tree_root *root, unsigned tag)
+{
+ set_bit(tag, root->tags);
+}
+
+static inline void
+root_tag_clear(struct radix_tree_root *root, unsigned tag)
+{
+ clear_bit(tag, root->tags);
+}
+
+static inline int
+tag_get(const struct radix_tree_node *node, unsigned int tag, int pos)
+{
+ return (test_bit(pos, node->tags[tag]));
+}
+
+static inline void
+tag_set(struct radix_tree_node *node, unsigned int tag, int pos)
+{
+ set_bit(pos, node->tags[tag]);
+}
+
+static inline void
+tag_clear(struct radix_tree_node *node, unsigned int tag, int pos)
+{
+ clear_bit(pos, node->tags[tag]);
+}
+
+static inline bool
+any_tag_set(const struct radix_tree_node *node, unsigned int tag)
+{
+ unsigned int pos;
+
+ for (pos = 0; pos < RADIX_TREE_TAG_LONGS; pos++)
+ if (node->tags[tag][pos])
+ return (true);
+
+ return (false);
+}
+
+static void
+node_tag_clear(struct radix_tree_root *root, struct radix_tree_node *stack[],
+ unsigned long index, unsigned int tag)
+{
+ struct radix_tree_node *node;
+ int height, pos;
+
+ height = 1;
+ node = stack[height];
+
+ while (node && height <= root->height - 1) {
+ pos = radix_pos(index, height);
+ if (!tag_get(node, tag, pos))
+ return;
+
+ tag_clear(node, tag, pos);
+ if (any_tag_set(node, tag))
+ return;
+
+ height++;
+ node = stack[height];
+ }
+
+ if (root_tag_get(root, tag))
+ root_tag_clear(root, tag);
+}
+
static void
radix_tree_clean_root_node(struct radix_tree_root *root)
{
@@ -84,14 +159,70 @@
return (item);
}
+unsigned int
+radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
+ unsigned long first_index, unsigned int max_items)
+{
+ struct radix_tree_iter iter;
+ void **slot;
+ int count;
+
+ count = 0;
+ if (max_items == 0)
+ return (count);
+
+ radix_tree_for_each_slot(slot, root, &iter, first_index) {
+ results[count] = *slot;
+ if (results[count] == NULL)
+ continue;
+
+ count++;
+ if (count == max_items)
+ break;
+ }
+
+ return (count);
+}
+
+unsigned int
+radix_tree_gang_lookup_tag(const struct radix_tree_root *root,
+ void **results, unsigned long first_index, unsigned int max_items,
+ unsigned int tag)
+{
+ struct radix_tree_iter iter;
+ void **slot;
+ int count;
+
+ count = 0;
+ if (max_items == 0)
+ return (count);
+
+ radix_tree_for_each_slot_tagged(slot, root, &iter, first_index, tag) {
+ results[count] = *slot;
+ if (results[count] == NULL)
+ continue;
+
+ count++;
+ if (count == max_items)
+ break;
+ }
+
+ return (count);
+}
+
bool
radix_tree_iter_find(const struct radix_tree_root *root,
- struct radix_tree_iter *iter, void ***pppslot)
+ struct radix_tree_iter *iter, void ***pppslot, int flags)
{
struct radix_tree_node *node;
unsigned long index = iter->index;
+ unsigned int tag;
int height;
+ tag = flags & RADIX_TREE_ITER_TAG_MASK;
+ if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
+ return (false);
+
restart:
node = root->rnode;
if (node == NULL)
@@ -109,7 +240,9 @@
*pppslot = node->slots + pos;
next = node->slots[pos];
- if (next == NULL) {
+ if (next == NULL ||
+ (flags & RADIX_TREE_ITER_TAGGED &&
+ !tag_get(next, tag, pos))) {
index += step;
index &= -step;
if ((index & mask) == 0)
@@ -131,6 +264,7 @@
void *item;
int height;
int idx;
+ int tag;
item = NULL;
node = root->rnode;
@@ -144,9 +278,15 @@
stack[height] = node;
node = node->slots[radix_pos(index, height--)];
}
- idx = radix_pos(index, 0);
- if (node)
+
+ if (node) {
+ idx = radix_pos(index, 0);
item = node->slots[idx];
+
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ node_tag_clear(root, stack, index, tag);
+ }
+
/*
* If we removed something reduce the height of the tree.
*/
@@ -380,3 +520,74 @@
node->count++;
return (0);
}
+
+void *
+radix_tree_tag_set(struct radix_tree_root *root, unsigned long index,
+ unsigned int tag)
+{
+ struct radix_tree_node *node;
+ void *item;
+ int height, pos;
+
+ item = NULL;
+ node = root->rnode;
+ height = root->height - 1;
+ if (index > radix_max(root))
+ goto out;
+
+ while (height) {
+ KASSERT(
+ node != NULL,
+ ("Node at index %lu does not exist in radix tree %p",
+ index, root));
+
+ pos = radix_pos(index, height--);
+ node = node->slots[pos];
+
+ if (!tag_get(node, tag, pos))
+ tag_set(node, tag, pos);
+ }
+
+ item = node->slots[radix_pos(index, 0)];
+
+ root_tag_set(root, tag);
+
+out:
+ return (item);
+}
+
+void *
+radix_tree_tag_clear(struct radix_tree_root *root,
+ unsigned long index, unsigned int tag)
+{
+ struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
+ struct radix_tree_node *node;
+ void *item;
+ int height;
+
+ item = NULL;
+ node = root->rnode;
+ height = root->height - 1;
+ if (index > radix_max(root))
+ goto out;
+
+ while (height && node) {
+ stack[height] = node;
+ node = node->slots[radix_pos(index, height--)];
+ }
+
+ if (node) {
+ item = node->slots[radix_pos(index, 0)];
+
+ node_tag_clear(root, stack, index, tag);
+ }
+
+out:
+ return (item);
+}
+
+int
+radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
+{
+ return (root_tag_get(root, tag));
+}
diff --git a/sys/compat/linuxkpi/common/src/linux_xarray.c b/sys/compat/linuxkpi/common/src/linux_xarray.c
--- a/sys/compat/linuxkpi/common/src/linux_xarray.c
+++ b/sys/compat/linuxkpi/common/src/linux_xarray.c
@@ -389,7 +389,7 @@
XA_ASSERT_LOCKED(xa);
- return (!radix_tree_iter_find(&xa->xa_head, &iter, &temp));
+ return (!radix_tree_iter_find(&xa->xa_head, &iter, &temp, 0));
}
bool
@@ -426,7 +426,7 @@
return (NULL);
}
- found = radix_tree_iter_find(&xa->xa_head, &iter, &ppslot);
+ found = radix_tree_iter_find(&xa->xa_head, &iter, &ppslot, 0);
if (likely(found)) {
retval = *ppslot;
if (retval == NULL_VALUE)

File Metadata

Mime Type
text/plain
Expires
Fri, Feb 13, 8:17 PM (5 h, 42 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
28020301
Default Alt Text
D54809.1771013862.diff (8 KB)

Event Timeline