[src/trunk]: src/sys/external/bsd/drm2/linux linux: Kludgily make radix tree ...

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

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

description:
linux: Kludgily make radix tree safe for RCU

Using a lock is completely stupid (gotta be cpu_simple_lock because
there's no radix_tree_destroy or anything), and the nonsense to do
unvolatile/unconst is garbage, but it will serve to make this safe
for RCU until someone makes our radix tree code RCU-safe (which
Someone^TM should totally do).

diffstat:

 sys/external/bsd/drm2/include/linux/radix-tree.h |  10 +-
 sys/external/bsd/drm2/linux/linux_radixtree.c    |  75 ++++++++++++++++++-----
 2 files changed, 65 insertions(+), 20 deletions(-)

diffs (214 lines):

diff -r 21c5e73ea1d0 -r af42e783a7a7 sys/external/bsd/drm2/include/linux/radix-tree.h
--- a/sys/external/bsd/drm2/include/linux/radix-tree.h  Sun Dec 19 11:51:43 2021 +0000
+++ b/sys/external/bsd/drm2/include/linux/radix-tree.h  Sun Dec 19 11:51:51 2021 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: radix-tree.h,v 1.7 2021/12/19 11:51:43 riastradh Exp $ */
+/*     $NetBSD: radix-tree.h,v 1.8 2021/12/19 11:51:51 riastradh Exp $ */
 
 /*-
  * Copyright (c) 2021 The NetBSD Foundation, Inc.
@@ -30,6 +30,7 @@
 #define _LINUX_RADIX_TREE_H_
 
 #include <sys/radixtree.h>
+#include <sys/lock.h>
 
 #include <linux/gfp.h>
 
@@ -45,12 +46,13 @@
 #define        radix_tree_next_slot            linux_radix_tree_next_slot
 
 struct radix_tree_root {
-       struct radix_tree rtr_tree;
+       struct radix_tree       rtr_tree;
+       __cpu_simple_lock_t     rtr_lock; /* XXX lame-o */
 };
 
 struct radix_tree_iter {
-       unsigned long           index;
-       struct radix_tree       *rti_tree;
+       unsigned long                   index;
+       const struct radix_tree_root    *rti_tree;
 };
 
 void   INIT_RADIX_TREE(struct radix_tree_root *, gfp_t);
diff -r 21c5e73ea1d0 -r af42e783a7a7 sys/external/bsd/drm2/linux/linux_radixtree.c
--- a/sys/external/bsd/drm2/linux/linux_radixtree.c     Sun Dec 19 11:51:43 2021 +0000
+++ b/sys/external/bsd/drm2/linux/linux_radixtree.c     Sun Dec 19 11:51:51 2021 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: linux_radixtree.c,v 1.1 2021/12/19 11:51:43 riastradh Exp $    */
+/*     $NetBSD: linux_radixtree.c,v 1.2 2021/12/19 11:51:51 riastradh Exp $    */
 
 /*-
  * Copyright (c) 2021 The NetBSD Foundation, Inc.
@@ -27,16 +27,25 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: linux_radixtree.c,v 1.1 2021/12/19 11:51:43 riastradh Exp $");
+__KERNEL_RCSID(0, "$NetBSD: linux_radixtree.c,v 1.2 2021/12/19 11:51:51 riastradh Exp $");
 
+#include <sys/atomic.h>
+#include <sys/kmem.h>
+#include <sys/lock.h>
 #include <sys/radixtree.h>
 
 #include <linux/gfp.h>
 #include <linux/radix-tree.h>
+#include <linux/rcupdate.h>
+#include <linux/slab.h>
+
+/* XXX mega-kludgerific */
+#define        __UNVOLANST(p)  ((void *)(unsigned long)(const volatile void *)(p))
 
 struct kludge {
        uint64_t        k_key;
        void            *k_datum;
+       struct rcu_head k_rcu;
 };
 
 void
@@ -44,21 +53,30 @@
 {
 
        radix_tree_init_tree(&root->rtr_tree);
+       __cpu_simple_lock_init(&root->rtr_lock);
 }
 
 int
 radix_tree_insert(struct radix_tree_root *root, unsigned long key, void *datum)
 {
        struct kludge *kludge;
+       int error;
 
-       if ((kludge = kmem_zalloc(sizeof(*kludge), KM_NOSLEEP)) == NULL)
+       /* XXX No way to know whether the caller can sleep or not...  */
+       if ((kludge = kzalloc(sizeof(*kludge), GFP_NOWAIT)) == NULL)
                return -ENOMEM;
 
        kludge->k_key = key;
        kludge->k_datum = datum;
 
+       membar_exit();
+
+       __cpu_simple_lock(&root->rtr_lock);
+       error = radix_tree_insert_node(&root->rtr_tree, key, kludge);
+       __cpu_simple_unlock(&root->rtr_lock);
+
        /* XXX errno NetBSD->Linux */
-       return -radix_tree_insert_node(&root->rtr_tree, key, kludge);
+       return -error;
 }
 
 void *
@@ -67,12 +85,14 @@
        struct kludge *kludge;
        void *datum = NULL;
 
-       if ((kludge = radix_tree_remove_node(&root->rtr_tree, key)) == NULL)
+       __cpu_simple_lock(&root->rtr_lock);
+       kludge = radix_tree_remove_node(&root->rtr_tree, key);
+       __cpu_simple_unlock(&root->rtr_lock);
+       if (kludge == NULL)
                return NULL;
 
-       /* XXX RCU defer */
        datum = kludge->k_datum;
-       kmem_free(kludge, sizeof(*kludge));
+       kfree_rcu(kludge, k_rcu);
 
        return datum;
 }
@@ -80,8 +100,13 @@
 bool
 radix_tree_empty(struct radix_tree_root *root)
 {
+       bool empty;
 
-       return radix_tree_empty_tree_p(&root->rtr_tree);
+       __cpu_simple_lock(&root->rtr_lock);
+       empty = radix_tree_empty_tree_p(&root->rtr_tree);
+       __cpu_simple_unlock(&root->rtr_lock);
+
+       return empty;
 }
 
 void *
@@ -89,9 +114,11 @@
 {
        struct kludge *kludge;
 
-       kludge = radix_tree_lookup_node(&root->rtr_tree, key);
+       __cpu_simple_lock(__UNVOLANST(&root->rtr_lock));
+       kludge = radix_tree_lookup_node(__UNVOLANST(&root->rtr_tree), key);
+       __cpu_simple_unlock(__UNVOLANST(&root->rtr_lock));
        if (kludge == NULL)
-               NULL;
+               return NULL;
 
        return kludge->k_datum;
 }
@@ -118,16 +145,21 @@
 {
        void *result;
        struct kludge *kludge;
+       unsigned nresults;
 
        KASSERT(flags == 0);
-       if (radix_tree_gang_lookup_node(&root->rtr_tree, I->index,
-               &result, /*maxresults*/1, /*dense*/false) == 0)
+       __cpu_simple_lock(__UNVOLANST(&root->rtr_lock));
+       nresults = radix_tree_gang_lookup_node(__UNVOLANST(&root->rtr_tree),
+           I->index, &result, /*maxresults*/1, /*dense*/false);
+       __cpu_simple_unlock(__UNVOLANST(&root->rtr_lock));
+       if (nresults == 0)
                return NULL;
+       KASSERT(nresults == 1);
 
        kludge = result;
 
        I->index = kludge->k_key;
-       I->rti_tree = &root->rtr_tree;
+       I->rti_tree = root;
        return &kludge->k_datum;
 }
 
@@ -136,17 +168,25 @@
 {
        struct kludge *kludge;
        void *result;
+       unsigned nresults;
 
        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)
+
+       __cpu_simple_lock(__UNVOLANST(&I->rti_tree->rtr_lock));
+       nresults = radix_tree_gang_lookup_node(
+           __UNVOLANST(&I->rti_tree->rtr_tree),
+           kludge->k_key, &result, /*maxresults*/1, /*dense*/true);
+       __cpu_simple_unlock(__UNVOLANST(&I->rti_tree->rtr_lock));
+       if (nresults == 0)
                return NULL;
+       KASSERT(nresults == 1);
 
        kludge = result;
 
        I->index = kludge->k_key;
-       I->rti_tree = &root->rtr_tree;
+       /* XXX Hope the tree hasn't changed!  */
        return &kludge->k_datum;
 }
 
@@ -157,6 +197,9 @@
        struct kludge *kludge = container_of(slot, struct kludge, k_datum);
        struct kludge *kludge0 __diagused;
 
+       __cpu_simple_lock(&root->rtr_lock);
        kludge0 = radix_tree_remove_node(&root->rtr_tree, kludge->k_key);
+       __cpu_simple_unlock(&root->rtr_lock);
+
        KASSERT(kludge0 == kludge);
 }