Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/riastradh-drm2]: src/sys/external/bsd/drm2 Rewrite idr to use a dumber a...



details:   https://anonhg.NetBSD.org/src/rev/e2fe6a4a3315
branches:  riastradh-drm2
changeset: 788584:e2fe6a4a3315
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Mon Dec 30 04:52:11 2013 +0000

description:
Rewrite idr to use a dumber algorithm that admits pserialized use.

drm2 doesn't use them with RCU, but it does use them under spin locks,
so an rwlock is not kosher.

This algorithm is super-dumb, but the idr API has changed upstream,
and this is not performance-critical, so it's not worth investing
time in a better algorithm at the moment.

diffstat:

 sys/external/bsd/drm2/include/linux/idr.h |   13 +-
 sys/external/bsd/drm2/linux/linux_idr.c   |  283 +++++++++++++++--------------
 2 files changed, 154 insertions(+), 142 deletions(-)

diffs (truncated from 402 to 300 lines):

diff -r 486b0eebe49f -r e2fe6a4a3315 sys/external/bsd/drm2/include/linux/idr.h
--- a/sys/external/bsd/drm2/include/linux/idr.h Mon Dec 30 04:52:02 2013 +0000
+++ b/sys/external/bsd/drm2/include/linux/idr.h Mon Dec 30 04:52:11 2013 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: idr.h,v 1.1.2.6 2013/07/24 03:13:59 riastradh Exp $    */
+/*     $NetBSD: idr.h,v 1.1.2.7 2013/12/30 04:52:11 riastradh Exp $    */
 
 /*-
  * Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -33,15 +33,16 @@
 #define _LINUX_IDR_H_
 
 #include <sys/types.h>
-#include <sys/rwlock.h>
-#include <sys/rbtree.h>
+#include <sys/mutex.h>
+#include <sys/pserialize.h>
 
 /* XXX Stupid expedient algorithm should be replaced by something better.  */
 
 struct idr {
-       krwlock_t idr_lock;
-       rb_tree_t idr_tree;
-       struct idr_node *idr_temp;
+       kmutex_t                idr_lock;
+       pserialize_t            idr_psz;
+       struct idr_state        *idr_state;
+       struct idr_state        *volatile idr_temp;
 };
 
 /* XXX Make the nm output a little more greppable...  */
diff -r 486b0eebe49f -r e2fe6a4a3315 sys/external/bsd/drm2/linux/linux_idr.c
--- a/sys/external/bsd/drm2/linux/linux_idr.c   Mon Dec 30 04:52:02 2013 +0000
+++ b/sys/external/bsd/drm2/linux/linux_idr.c   Mon Dec 30 04:52:11 2013 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: linux_idr.c,v 1.1.2.9 2013/07/24 04:02:58 riastradh Exp $      */
+/*     $NetBSD: linux_idr.c,v 1.1.2.10 2013/12/30 04:52:11 riastradh Exp $     */
 
 /*-
  * Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -30,215 +30,226 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.1.2.9 2013/07/24 04:02:58 riastradh Exp $");
+__KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.1.2.10 2013/12/30 04:52:11 riastradh Exp $");
 
 #include <sys/param.h>
 #include <sys/atomic.h>
-#include <sys/kmem.h>
-#include <sys/rbtree.h>
+#include <sys/mutex.h>
+#include <sys/pserialize.h>
 
 #include <linux/err.h>
 #include <linux/idr.h>
-
-struct idr_node {
-       rb_node_t in_rb_node;
-       int in_index;
-       void *in_data;
-};
-
-static signed int idr_tree_compare_nodes(void *, const void *, const void *);
-static signed int idr_tree_compare_key(void *, const void *, const void *);
-
-static const rb_tree_ops_t idr_rb_ops = {
-       .rbto_compare_nodes = &idr_tree_compare_nodes,
-       .rbto_compare_key = &idr_tree_compare_key,
-       .rbto_node_offset = offsetof(struct idr_node, in_rb_node),
-       .rbto_context = NULL,
-};
+#include <linux/slab.h>
 
-static signed int
-idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb)
-{
-       const int a = ((const struct idr_node *)na)->in_index;
-       const int b = ((const struct idr_node *)nb)->in_index;
-
-       if (a < b)
-               return -1;
-       else if (b < a)
-                return +1;
-       else
-               return 0;
-}
-
-static signed int
-idr_tree_compare_key(void *ctx __unused, const void *n, const void *key)
-{
-       const int a = ((const struct idr_node *)n)->in_index;
-       const int b = *(const int *)key;
-
-       if (a < b)
-               return -1;
-       else if (b < a)
-               return +1;
-       else
-               return 0;
-}
+struct idr_state {
+       size_t                  is_n_allocated;
+       size_t                  is_n_used;
+       void                    **is_data;
+};
 
 void
 idr_init(struct idr *idr)
 {
 
-       rw_init(&idr->idr_lock);
-       rb_tree_init(&idr->idr_tree, &idr_rb_ops);
+       mutex_init(&idr->idr_lock, MUTEX_DEFAULT, IPL_VM);
+       idr->idr_psz = pserialize_create();
+       idr->idr_state = kmalloc(sizeof(*idr->idr_state), GFP_KERNEL);
+       KASSERT(idr->idr_state != NULL);
+       idr->idr_state->is_n_allocated = 1;
+       idr->idr_state->is_n_used = 0;
+       idr->idr_state->is_data = kcalloc(1, sizeof(void *), GFP_KERNEL);
+       KASSERT(idr->idr_state->is_data != NULL);
        idr->idr_temp = NULL;
 }
 
+static struct idr_state *
+idr_state(struct idr *idr)
+{
+       struct idr_state *const is = idr->idr_state;
+
+       membar_consumer();              /* match state */
+
+       return is;
+}
+
 void
 idr_destroy(struct idr *idr)
 {
+       struct idr_state *const is = idr_state(idr);
 
-       if (idr->idr_temp != NULL) {
-               /* XXX Probably shouldn't happen.  */
-               kmem_free(idr->idr_temp, sizeof(*idr->idr_temp));
-               idr->idr_temp = NULL;
-       }
-#if 0                          /* XXX No rb_tree_destroy?  */
-       rb_tree_destroy(&idr->idr_tree);
-#endif
-       rw_destroy(&idr->idr_lock);
+       kfree(is->is_data);
+       kfree(is);
+       KASSERT(idr->idr_temp == NULL);
+
+       pserialize_destroy(idr->idr_psz);
+       mutex_destroy(&idr->idr_lock);
+}
+
+static void **
+idr_find_ptr(struct idr *idr, int id)
+{
+       if (id < 0)
+               return NULL;
+
+       struct idr_state *const is = idr_state(idr);
+       if (is->is_n_used <= id)
+               return NULL;
+
+       return &is->is_data[id];
 }
 
 void *
 idr_find(struct idr *idr, int id)
 {
-       const struct idr_node *node;
-       void *data;
+       void **const ptr = idr_find_ptr(idr, id);
+
+       if (ptr == NULL)
+               return NULL;
 
-       rw_enter(&idr->idr_lock, RW_READER);
-       node = rb_tree_find_node(&idr->idr_tree, &id);
-       data = (node == NULL? NULL : node->in_data);
-       rw_exit(&idr->idr_lock);
+       void *const datum = *ptr;
 
-       return data;
+       membar_consumer();              /* match datum */
+       return datum;
 }
 
 void *
 idr_replace(struct idr *idr, void *replacement, int id)
 {
-       struct idr_node *node;
-       void *result;
+       void **const ptr = idr_find_ptr(idr, id);
+
+       if (ptr == NULL)
+               return ERR_PTR(-ENOENT);
 
-       rw_enter(&idr->idr_lock, RW_WRITER);
-       node = rb_tree_find_node(&idr->idr_tree, &id);
-       if (node == NULL) {
-               result = ERR_PTR(-ENOENT);
-       } else {
-               result = node->in_data;
-               node->in_data = replacement;
-       }
-       rw_exit(&idr->idr_lock);
+       void *const datum = *ptr;
 
-       return result;
+       membar_producer();              /* match datum */
+       *ptr = replacement;
+
+       return datum;
 }
 
 void
 idr_remove(struct idr *idr, int id)
 {
-       struct idr_node *node;
+       if (id < 0)
+               return;
+
+       struct idr_state *const is = idr_state(idr);
+
+       if (is->is_n_used < id)
+               return;
 
-       rw_enter(&idr->idr_lock, RW_WRITER);
-       node = rb_tree_find_node(&idr->idr_tree, &id);
-       KASSERT(node != NULL);
-       rb_tree_remove_node(&idr->idr_tree, node);
-       rw_exit(&idr->idr_lock);
-       kmem_free(node, sizeof(*node));
+       is->is_data[id] = NULL;
+
+       if ((id + 1) == is->is_n_used) {
+               while ((0 < id--) && (is->is_data[id] == NULL))
+                       continue;
+               is->is_n_used = id;
+       }
 }
 
 void
 idr_remove_all(struct idr *idr)
 {
-       struct idr_node *node;
+       struct idr_state *const is = idr_state(idr);
 
-       rw_enter(&idr->idr_lock, RW_WRITER);
-       while ((node = RB_TREE_MIN(&idr->idr_tree)) != NULL) {
-               rb_tree_remove_node(&idr->idr_tree, node);
-               rw_exit(&idr->idr_lock);
-               kmem_free(node, sizeof(*node));
-               rw_enter(&idr->idr_lock, RW_WRITER);
-       }
-       rw_exit(&idr->idr_lock);
+       is->is_n_used = 0;
 }
 
 int
-idr_pre_get(struct idr *idr, int flags __unused /* XXX */)
+idr_pre_get(struct idr *idr, gfp_t gfp)
 {
-       struct idr_node *temp = kmem_alloc(sizeof(*temp), KM_SLEEP);
+       struct idr_state *old_is, *new_is, *temp_is;
+       size_t n_used;
+
+       old_is = idr_state(idr);
+       n_used = old_is->is_n_used;
 
-       rw_enter(&idr->idr_lock, RW_WRITER);
-       if (idr->idr_temp == NULL) {
-               idr->idr_temp = temp;
-               temp = NULL;
+       new_is = kmalloc(sizeof(*new_is), gfp);
+       if (new_is == NULL)
+               return 0;
+       new_is->is_data = kcalloc((n_used + 1), sizeof(*new_is->is_data), gfp);
+       if (new_is->is_data == NULL) {
+               kfree(new_is);
+               return 0;
        }
-       rw_exit(&idr->idr_lock);
+
+       new_is->is_n_allocated = (n_used + 1);
+
+       membar_producer();              /* match temp */
 
-       if (temp != NULL)
-               kmem_free(temp, sizeof(*temp));
+       /*
+        * If someone already put one in, replace it -- we're probably
+        * more up-to-date.
+        */
+       temp_is = atomic_swap_ptr(&idr->idr_temp, new_is);
+       if (temp_is != NULL) {
+               membar_consumer();      /* match temp */



Home | Main Index | Thread Index | Old Index