Module Name: src
Committed By: riastradh
Date: Sun Dec 19 12:05:25 UTC 2021
Modified Files:
src/sys/external/bsd/drm2/include/linux: xarray.h
src/sys/external/bsd/drm2/linux: linux_xa.c
Log Message:
linux: Rework radix tree shims.
To generate a diff of this commit:
cvs rdiff -u -r1.8 -r1.9 src/sys/external/bsd/drm2/include/linux/xarray.h
cvs rdiff -u -r1.2 -r1.3 src/sys/external/bsd/drm2/linux/linux_xa.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/external/bsd/drm2/include/linux/xarray.h
diff -u src/sys/external/bsd/drm2/include/linux/xarray.h:1.8 src/sys/external/bsd/drm2/include/linux/xarray.h:1.9
--- src/sys/external/bsd/drm2/include/linux/xarray.h:1.8 Sun Dec 19 11:51:07 2021
+++ src/sys/external/bsd/drm2/include/linux/xarray.h Sun Dec 19 12:05:25 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: xarray.h,v 1.8 2021/12/19 11:51:07 riastradh Exp $ */
+/* $NetBSD: xarray.h,v 1.9 2021/12/19 12:05:25 riastradh Exp $ */
/*-
* Copyright (c) 2020 The NetBSD Foundation, Inc.
@@ -29,7 +29,7 @@
#ifndef _LINUX_XARRAY_H_
#define _LINUX_XARRAY_H_
-#include <sys/radixtree.h>
+#include <sys/rbtree.h>
#include <linux/slab.h>
@@ -43,14 +43,14 @@ struct xa_limit {
struct xarray {
kmutex_t xa_lock;
- struct radix_tree xa_tree;
+ struct rb_tree xa_tree;
gfp_t xa_gfp;
};
#define xa_for_each(XA, INDEX, ENTRY) \
for ((INDEX) = 0, (ENTRY) = xa_find((XA), &(INDEX), ULONG_MAX, -1); \
(ENTRY) != NULL; \
- (ENTRY) = xa_find_after((XA), &(INDEX), ULONG_MAX, 0))
+ (ENTRY) = xa_find_after((XA), &(INDEX), ULONG_MAX, -1))
#define XA_ERROR(error) ((void *)(((uintptr_t)error << 2) | 2))
Index: src/sys/external/bsd/drm2/linux/linux_xa.c
diff -u src/sys/external/bsd/drm2/linux/linux_xa.c:1.2 src/sys/external/bsd/drm2/linux/linux_xa.c:1.3
--- src/sys/external/bsd/drm2/linux/linux_xa.c:1.2 Sun Dec 19 12:05:18 2021
+++ src/sys/external/bsd/drm2/linux/linux_xa.c Sun Dec 19 12:05:25 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: linux_xa.c,v 1.2 2021/12/19 12:05:18 riastradh Exp $ */
+/* $NetBSD: linux_xa.c,v 1.3 2021/12/19 12:05:25 riastradh Exp $ */
/*-
* Copyright (c) 2021 The NetBSD Foundation, Inc.
@@ -27,14 +27,59 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: linux_xa.c,v 1.2 2021/12/19 12:05:18 riastradh Exp $");
+__KERNEL_RCSID(0, "$NetBSD: linux_xa.c,v 1.3 2021/12/19 12:05:25 riastradh Exp $");
-#include <sys/radixtree.h>
+/*
+ * This is a lame-o implementation of the Linux xarray data type, which
+ * implements a map from 64-bit integers to pointers. The operations
+ * it supports are designed to be implemented by a radix tree, but
+ * NetBSD's radixtree(9) doesn't quite support them all, and it's a bit
+ * of work to implement them, so this just uses a red/black tree
+ * instead at the cost of some performance in certain types of lookups
+ * (and negative-lookups -- finding a free key).
+ */
-#include <uvm/uvm_pdaemon.h>
+#include <sys/rbtree.h>
#include <linux/xarray.h>
+struct node {
+ struct rb_node n_rb;
+ uint64_t n_key;
+ void *n_datum;
+};
+
+static int
+compare_nodes(void *cookie, const void *va, const void *vb)
+{
+ const struct node *a = va, *b = vb;
+
+ if (a->n_key < b->n_key)
+ return -1;
+ if (a->n_key > b->n_key)
+ return +1;
+ return 0;
+}
+
+static int
+compare_node_key(void *cookie, const void *vn, const void *vk)
+{
+ const struct node *n = vn;
+ const uint64_t *k = vk;
+
+ if (n->n_key < *k)
+ return -1;
+ if (n->n_key > *k)
+ return +1;
+ return 0;
+}
+
+static const rb_tree_ops_t xa_rb_ops = {
+ .rbto_compare_nodes = compare_nodes,
+ .rbto_compare_key = compare_node_key,
+ .rbto_node_offset = offsetof(struct node, n_rb),
+};
+
const struct xa_limit xa_limit_32b = { .min = 0, .max = UINT32_MAX };
void
@@ -42,91 +87,102 @@ xa_init_flags(struct xarray *xa, gfp_t g
{
mutex_init(&xa->xa_lock, MUTEX_DEFAULT, IPL_VM);
- radix_tree_init_tree(&xa->xa_tree);
+ rb_tree_init(&xa->xa_tree, &xa_rb_ops);
xa->xa_gfp = gfp;
}
void
xa_destroy(struct xarray *xa)
{
+ struct node *n;
- KASSERT(radix_tree_empty_tree_p(&xa->xa_tree));
- radix_tree_fini_tree(&xa->xa_tree);
+ /*
+ * Linux allows xa to remain populated on destruction; it is
+ * our job to free any internal node structures.
+ */
+ while ((n = RB_TREE_MIN(&xa->xa_tree)) != NULL) {
+ rb_tree_remove_node(&xa->xa_tree, n);
+ kmem_free(n, sizeof(*n));
+ }
mutex_destroy(&xa->xa_lock);
}
void *
xa_load(struct xarray *xa, unsigned long key)
{
- void *datum;
+ const uint64_t key64 = key;
+ struct node *n;
/* XXX pserialize */
mutex_enter(&xa->xa_lock);
- datum = radix_tree_lookup_node(&xa->xa_tree, key);
+ n = rb_tree_find_node(&xa->xa_tree, &key64);
mutex_exit(&xa->xa_lock);
- return datum;
+ return n ? n->n_datum : NULL;
}
void *
xa_store(struct xarray *xa, unsigned long key, void *datum, gfp_t gfp)
{
- void *collision;
- int error;
+ struct node *n, *collision;
KASSERT(datum != NULL);
KASSERT(((uintptr_t)datum & 0x3) == 0);
-retry: mutex_enter(&xa->xa_lock);
- collision = radix_tree_lookup_node(&xa->xa_tree, key);
- error = radix_tree_insert_node(&xa->xa_tree, key, datum);
+ n = kmem_zalloc(sizeof(*n), gfp & __GFP_WAIT ? KM_SLEEP : KM_NOSLEEP);
+ if (n == NULL)
+ return XA_ERROR(-ENOMEM);
+ n->n_key = key;
+ n->n_datum = datum;
+
+ mutex_enter(&xa->xa_lock);
+ collision = rb_tree_insert_node(&xa->xa_tree, n);
mutex_exit(&xa->xa_lock);
- if (error) {
- if (gfp & __GFP_WAIT) {
- uvm_wait("xa");
- goto retry;
- }
- /* XXX errno NetBSD->Linux */
- return XA_ERROR(-error);
- }
- return collision;
+ if (collision != n) {
+ datum = collision->n_datum;
+ kmem_free(collision, sizeof(*collision));
+ }
+ return datum;
}
int
xa_alloc(struct xarray *xa, uint32_t *idp, void *datum, struct xa_limit limit,
gfp_t gfp)
{
- uint32_t key = limit.min;
- void *collision;
+ uint64_t key64 = limit.min;
+ struct node *n, *n1, *collision __diagused;
int error;
KASSERTMSG(limit.min < limit.max, "min=%"PRIu32" max=%"PRIu32,
limit.min, limit.max);
-retry: mutex_enter(&xa->xa_lock);
- /* XXX use the radix tree to make this fast */
- while ((collision = radix_tree_lookup_node(&xa->xa_tree, key))
- != NULL) {
- if (key++ == limit.max)
- goto out;
- }
- error = radix_tree_insert_node(&xa->xa_tree, key, datum);
-out: mutex_exit(&xa->xa_lock);
+ n = kmem_zalloc(sizeof(*n), gfp & __GFP_WAIT ? KM_SLEEP : KM_NOSLEEP);
+ if (n == NULL)
+ return -ENOMEM;
+ n->n_datum = datum;
- if (collision)
- return -EBUSY;
- if (error) {
- if (gfp & __GFP_WAIT) {
- uvm_wait("xa");
- goto retry;
+ mutex_enter(&xa->xa_lock);
+ while ((n1 = rb_tree_find_node_geq(&xa->xa_tree, &key64)) != NULL &&
+ n1->n_key == key64) {
+ if (key64 == limit.max) {
+ error = -EBUSY;
+ goto out;
}
- /* XXX errno NetBSD->Linux */
- return -error;
+ KASSERT(key64 < UINT32_MAX);
+ key64++;
}
+ /* Found a hole -- insert in it. */
+ KASSERT(n1 == NULL || n1->n_key > key64);
+ n->n_key = key64;
+ collision = rb_tree_insert_node(&xa->xa_tree, n);
+ KASSERT(collision == n);
+ error = 0;
+out: mutex_exit(&xa->xa_lock);
- /* Success! */
- *idp = key;
+ if (error)
+ return error;
+ *idp = key64;
return 0;
}
@@ -134,23 +190,20 @@ void *
xa_find(struct xarray *xa, unsigned long *startp, unsigned long max,
unsigned tagmask)
{
- uint64_t key = *startp;
- void *candidate = NULL;
+ uint64_t key64 = *startp;
+ struct node *n = NULL;
+
+ KASSERT(tagmask == -1); /* not yet supported */
mutex_enter(&xa->xa_lock);
- for (; key < max; key++, candidate = NULL) {
- candidate = radix_tree_lookup_node(&xa->xa_tree, key);
- if (candidate == NULL)
- continue;
- if (tagmask == -1 ||
- radix_tree_get_tag(&xa->xa_tree, key, tagmask))
- break;
- }
+ n = rb_tree_find_node_geq(&xa->xa_tree, &key64);
mutex_exit(&xa->xa_lock);
- if (candidate)
- *startp = key;
- return candidate;
+ if (n == NULL || n->n_key > max)
+ return NULL;
+
+ *startp = n->n_key;
+ return n->n_datum;
}
void *
@@ -171,11 +224,19 @@ xa_find_after(struct xarray *xa, unsigne
void *
xa_erase(struct xarray *xa, unsigned long key)
{
- void *datum;
+ uint64_t key64 = key;
+ struct node *n;
+ void *datum = NULL;
mutex_enter(&xa->xa_lock);
- datum = radix_tree_remove_node(&xa->xa_tree, key);
+ n = rb_tree_find_node(&xa->xa_tree, &key64);
+ if (n)
+ rb_tree_remove_node(&xa->xa_tree, n);
mutex_exit(&xa->xa_lock);
+ if (n) {
+ datum = n->n_datum;
+ kmem_free(n, sizeof(*n));
+ }
return datum;
}
