[src/trunk]: src/sys/external/bsd/drm2/linux linux: Kludgey radix tree shims

[riastradh <riastradh%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/21c5e73ea1d0
branches:  trunk
changeset: 1028722:21c5e73ea1d0
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Sun Dec 19 11:51:43 2021 +0000

description:
linux: Kludgey radix tree shims

diffstat:

 sys/external/bsd/drm2/include/linux/radix-tree.h |   19 +-
 sys/external/bsd/drm2/linux/files.drmkms_linux   |    3 +-
 sys/external/bsd/drm2/linux/linux_radixtree.c    |  162 +++++++++++++++++++++++
 3 files changed, 173 insertions(+), 11 deletions(-)

diffs (251 lines):

diff -r a2060cfc3887 -r 21c5e73ea1d0 sys/external/bsd/drm2/include/linux/radix-tree.h
--- a/sys/external/bsd/drm2/include/linux/radix-tree.h  Sun Dec 19 11:51:32 2021 +0000
+++ b/sys/external/bsd/drm2/include/linux/radix-tree.h  Sun Dec 19 11:51:43 2021 +0000
@@ -1,12 +1,9 @@
-/*     $NetBSD: radix-tree.h,v 1.6 2021/12/19 11:50:31 riastradh Exp $ */
+/*     $NetBSD: radix-tree.h,v 1.7 2021/12/19 11:51:43 riastradh Exp $ */
 
 /*-
- * Copyright (c) 2018 The NetBSD Foundation, Inc.
+ * Copyright (c) 2021 The NetBSD Foundation, Inc.
  * All rights reserved.
  *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Taylor R. Campbell.
- *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
@@ -32,13 +29,14 @@
 #ifndef _LINUX_RADIX_TREE_H_
 #define _LINUX_RADIX_TREE_H_
 
+#include <sys/radixtree.h>
+
 #include <linux/gfp.h>
 
 #define        INIT_RADIX_TREE                 linux_INIT_RADIX_TREE
 #define        radix_tree_delete               linux_radix_tree_delete
 #define        radix_tree_deref_slot           linux_radix_tree_deref_slot
 #define        radix_tree_empty                linux_radix_tree_empty
-#define        radix_tree_exception            linux_radix_tree_exception
 #define        radix_tree_insert               linux_radix_tree_insert
 #define        radix_tree_iter_delete          linux_radix_tree_iter_delete
 #define        radix_tree_iter_init            linux_radix_tree_iter_init
@@ -47,28 +45,29 @@
 #define        radix_tree_next_slot            linux_radix_tree_next_slot
 
 struct radix_tree_root {
+       struct radix_tree rtr_tree;
 };
 
 struct radix_tree_iter {
-       unsigned long index;
+       unsigned long           index;
+       struct radix_tree       *rti_tree;
 };
 
 void   INIT_RADIX_TREE(struct radix_tree_root *, gfp_t);
 
 int    radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
-void   radix_tree_iter_delete(struct radix_tree_root *,
-           struct radix_tree_iter *, void **);
 void * radix_tree_delete(struct radix_tree_root *, unsigned long);
 
 bool   radix_tree_empty(struct radix_tree_root *);
 void * radix_tree_lookup(const struct radix_tree_root *, unsigned long);
-bool   radix_tree_exception(void *);
 void * radix_tree_deref_slot(void **);
 
 void **        radix_tree_iter_init(struct radix_tree_iter *, unsigned long);
 void **        radix_tree_next_chunk(const struct radix_tree_root *,
            struct radix_tree_iter *, unsigned);
 void **        radix_tree_next_slot(void **, struct radix_tree_iter *, unsigned);
+void   radix_tree_iter_delete(struct radix_tree_root *,
+           struct radix_tree_iter *, void **);
 
 #define        radix_tree_for_each_slot(N, T, I, S)                                  \
        for ((N) = radix_tree_iter_init((I), (S));                            \
diff -r a2060cfc3887 -r 21c5e73ea1d0 sys/external/bsd/drm2/linux/files.drmkms_linux
--- a/sys/external/bsd/drm2/linux/files.drmkms_linux    Sun Dec 19 11:51:32 2021 +0000
+++ b/sys/external/bsd/drm2/linux/files.drmkms_linux    Sun Dec 19 11:51:43 2021 +0000
@@ -1,4 +1,4 @@
-#       $NetBSD: files.drmkms_linux,v 1.36 2021/12/19 11:51:07 riastradh Exp $
+#       $NetBSD: files.drmkms_linux,v 1.37 2021/12/19 11:51:43 riastradh Exp $
 
 define drmkms_linux: i2cexec, i2c_bitbang
 
@@ -23,6 +23,7 @@
 file   external/bsd/drm2/linux/linux_module.c          drmkms_linux
 file   external/bsd/drm2/linux/linux_notifier.c        drmkms_linux
 file   external/bsd/drm2/linux/linux_pci.c             drmkms_linux
+file   external/bsd/drm2/linux/linux_radixtree.c       drmkms_linux
 file   external/bsd/drm2/linux/linux_rwsem.c           drmkms_linux
 file   external/bsd/drm2/linux/linux_sg.c              drmkms_linux
 file   external/bsd/drm2/linux/linux_stop_machine.c    drmkms_linux
diff -r a2060cfc3887 -r 21c5e73ea1d0 sys/external/bsd/drm2/linux/linux_radixtree.c
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/external/bsd/drm2/linux/linux_radixtree.c     Sun Dec 19 11:51:43 2021 +0000
@@ -0,0 +1,162 @@
+/*     $NetBSD: linux_radixtree.c,v 1.1 2021/12/19 11:51:43 riastradh Exp $    */
+
+/*-
+ * Copyright (c) 2021 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: linux_radixtree.c,v 1.1 2021/12/19 11:51:43 riastradh Exp $");
+
+#include <sys/radixtree.h>
+
+#include <linux/gfp.h>
+#include <linux/radix-tree.h>
+
+struct kludge {
+       uint64_t        k_key;
+       void            *k_datum;
+};
+
+void
+INIT_RADIX_TREE(struct radix_tree_root *root, gfp_t gfp)
+{
+
+       radix_tree_init_tree(&root->rtr_tree);
+}
+
+int
+radix_tree_insert(struct radix_tree_root *root, unsigned long key, void *datum)
+{
+       struct kludge *kludge;
+
+       if ((kludge = kmem_zalloc(sizeof(*kludge), KM_NOSLEEP)) == NULL)
+               return -ENOMEM;
+
+       kludge->k_key = key;
+       kludge->k_datum = datum;
+
+       /* XXX errno NetBSD->Linux */
+       return -radix_tree_insert_node(&root->rtr_tree, key, kludge);
+}
+
+void *
+radix_tree_delete(struct radix_tree_root *root, unsigned long key)
+{
+       struct kludge *kludge;
+       void *datum = NULL;
+
+       if ((kludge = radix_tree_remove_node(&root->rtr_tree, key)) == NULL)
+               return NULL;
+
+       /* XXX RCU defer */
+       datum = kludge->k_datum;
+       kmem_free(kludge, sizeof(*kludge));
+
+       return datum;
+}
+
+bool
+radix_tree_empty(struct radix_tree_root *root)
+{
+
+       return radix_tree_empty_tree_p(&root->rtr_tree);
+}
+
+void *
+radix_tree_lookup(const struct radix_tree_root *root, unsigned long key)
+{
+       struct kludge *kludge;
+
+       kludge = radix_tree_lookup_node(&root->rtr_tree, key);
+       if (kludge == NULL)
+               NULL;
+
+       return kludge->k_datum;
+}
+
+void *
+radix_tree_deref_slot(void **slot)
+{
+
+       return atomic_load_consume(slot);
+}
+
+void **
+radix_tree_iter_init(struct radix_tree_iter *I, unsigned long start)
+{
+
+       I->index = start;
+       I->rti_tree = NULL;
+       return NULL;
+}
+
+void **
+radix_tree_next_chunk(const struct radix_tree_root *root,
+    struct radix_tree_iter *I, unsigned flags)
+{
+       void *result;
+       struct kludge *kludge;
+
+       KASSERT(flags == 0);
+       if (radix_tree_gang_lookup_node(&root->rtr_tree, I->index,
+               &result, /*maxresults*/1, /*dense*/false) == 0)
+               return NULL;
+
+       kludge = result;
+
+       I->index = kludge->k_key;
+       I->rti_tree = &root->rtr_tree;
+       return &kludge->k_datum;
+}
+
+void **
+radix_tree_next_slot(void **slot, struct radix_tree_iter *I, unsigned flags)
+{
+       struct kludge *kludge;
+       void *result;
+
+       KASSERT(flags == 0);
+       kludge = container_of(slot, struct kludge, k_datum);
+       if (radix_tree_gang_lookup_node(I->rtr_tree, kludge->k_key,
+               &result, /*maxresults*/1, /*dense*/true) == 0)
+               return NULL;
+
+       kludge = result;
+
+       I->index = kludge->k_key;
+       I->rti_tree = &root->rtr_tree;
+       return &kludge->k_datum;
+}
+
+void
+radix_tree_iter_delete(struct radix_tree_root *root, struct radix_tree_iter *I,
+    void **slot)
+{
+       struct kludge *kludge = container_of(slot, struct kludge, k_datum);
+       struct kludge *kludge0 __diagused;
+
+       kludge0 = radix_tree_remove_node(&root->rtr_tree, kludge->k_key);
+       KASSERT(kludge0 == kludge);
+}