Module Name: src
Committed By: riastradh
Date: Wed Jan 15 13:51:48 UTC 2014
Modified Files:
src/sys/external/bsd/drm2/include/linux [riastradh-drm2]: idr.h
src/sys/external/bsd/drm2/linux [riastradh-drm2]: linux_idr.c
Log Message:
Revert "Rewrite idr to use a dumber algorithm that admits pserialized use."
This reverts commit 3a389a1cb20777fb73575f0514b96265052ac1ea.
I don't know what I was smoking with this; just need to change the
rwlock to a spin lock and we'll be good!
To generate a diff of this commit:
cvs rdiff -u -r1.1.2.7 -r1.1.2.8 \
src/sys/external/bsd/drm2/include/linux/idr.h
cvs rdiff -u -r1.1.2.10 -r1.1.2.11 \
src/sys/external/bsd/drm2/linux/linux_idr.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/idr.h
diff -u src/sys/external/bsd/drm2/include/linux/idr.h:1.1.2.7 src/sys/external/bsd/drm2/include/linux/idr.h:1.1.2.8
--- src/sys/external/bsd/drm2/include/linux/idr.h:1.1.2.7 Mon Dec 30 04:52:11 2013
+++ src/sys/external/bsd/drm2/include/linux/idr.h Wed Jan 15 13:51:48 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: idr.h,v 1.1.2.7 2013/12/30 04:52:11 riastradh Exp $ */
+/* $NetBSD: idr.h,v 1.1.2.8 2014/01/15 13:51:48 riastradh Exp $ */
/*-
* Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -33,16 +33,15 @@
#define _LINUX_IDR_H_
#include <sys/types.h>
-#include <sys/mutex.h>
-#include <sys/pserialize.h>
+#include <sys/rwlock.h>
+#include <sys/rbtree.h>
/* XXX Stupid expedient algorithm should be replaced by something better. */
struct idr {
- kmutex_t idr_lock;
- pserialize_t idr_psz;
- struct idr_state *idr_state;
- struct idr_state *volatile idr_temp;
+ krwlock_t idr_lock;
+ rb_tree_t idr_tree;
+ struct idr_node *idr_temp;
};
/* XXX Make the nm output a little more greppable... */
Index: src/sys/external/bsd/drm2/linux/linux_idr.c
diff -u src/sys/external/bsd/drm2/linux/linux_idr.c:1.1.2.10 src/sys/external/bsd/drm2/linux/linux_idr.c:1.1.2.11
--- src/sys/external/bsd/drm2/linux/linux_idr.c:1.1.2.10 Mon Dec 30 04:52:11 2013
+++ src/sys/external/bsd/drm2/linux/linux_idr.c Wed Jan 15 13:51:48 2014
@@ -1,4 +1,4 @@
-/* $NetBSD: linux_idr.c,v 1.1.2.10 2013/12/30 04:52:11 riastradh Exp $ */
+/* $NetBSD: linux_idr.c,v 1.1.2.11 2014/01/15 13:51:48 riastradh Exp $ */
/*-
* Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -30,226 +30,215 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.1.2.10 2013/12/30 04:52:11 riastradh Exp $");
+__KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.1.2.11 2014/01/15 13:51:48 riastradh Exp $");
#include <sys/param.h>
#include <sys/atomic.h>
-#include <sys/mutex.h>
-#include <sys/pserialize.h>
+#include <sys/kmem.h>
+#include <sys/rbtree.h>
#include <linux/err.h>
#include <linux/idr.h>
-#include <linux/slab.h>
-struct idr_state {
- size_t is_n_allocated;
- size_t is_n_used;
- void **is_data;
+struct idr_node {
+ rb_node_t in_rb_node;
+ int in_index;
+ void *in_data;
};
-void
-idr_init(struct idr *idr)
+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,
+};
+
+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;
- 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;
+ if (a < b)
+ return -1;
+ else if (b < a)
+ return +1;
+ else
+ return 0;
}
-static struct idr_state *
-idr_state(struct idr *idr)
+static signed int
+idr_tree_compare_key(void *ctx __unused, const void *n, const void *key)
{
- struct idr_state *const is = idr->idr_state;
-
- membar_consumer(); /* match state */
+ const int a = ((const struct idr_node *)n)->in_index;
+ const int b = *(const int *)key;
- return is;
+ if (a < b)
+ return -1;
+ else if (b < a)
+ return +1;
+ else
+ return 0;
}
void
-idr_destroy(struct idr *idr)
+idr_init(struct idr *idr)
{
- struct idr_state *const is = idr_state(idr);
-
- kfree(is->is_data);
- kfree(is);
- KASSERT(idr->idr_temp == NULL);
- pserialize_destroy(idr->idr_psz);
- mutex_destroy(&idr->idr_lock);
+ rw_init(&idr->idr_lock);
+ rb_tree_init(&idr->idr_tree, &idr_rb_ops);
+ idr->idr_temp = NULL;
}
-static void **
-idr_find_ptr(struct idr *idr, int id)
+void
+idr_destroy(struct idr *idr)
{
- 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];
+ 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);
}
void *
idr_find(struct idr *idr, int id)
{
- void **const ptr = idr_find_ptr(idr, id);
-
- if (ptr == NULL)
- return NULL;
+ const struct idr_node *node;
+ void *data;
- void *const datum = *ptr;
+ 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);
- membar_consumer(); /* match datum */
- return datum;
+ return data;
}
void *
idr_replace(struct idr *idr, void *replacement, int id)
{
- void **const ptr = idr_find_ptr(idr, id);
-
- if (ptr == NULL)
- return ERR_PTR(-ENOENT);
+ struct idr_node *node;
+ void *result;
- void *const datum = *ptr;
-
- membar_producer(); /* match datum */
- *ptr = replacement;
+ 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);
- return datum;
+ return result;
}
void
idr_remove(struct idr *idr, int id)
{
- if (id < 0)
- return;
+ struct idr_node *node;
- struct idr_state *const is = idr_state(idr);
-
- if (is->is_n_used < id)
- return;
-
- 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;
- }
+ 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));
}
void
idr_remove_all(struct idr *idr)
{
- struct idr_state *const is = idr_state(idr);
+ struct idr_node *node;
- is->is_n_used = 0;
+ 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);
}
int
-idr_pre_get(struct idr *idr, gfp_t gfp)
+idr_pre_get(struct idr *idr, int flags __unused /* XXX */)
{
- struct idr_state *old_is, *new_is, *temp_is;
- size_t n_used;
+ struct idr_node *temp = kmem_alloc(sizeof(*temp), KM_SLEEP);
- old_is = idr_state(idr);
- n_used = old_is->is_n_used;
-
- 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_enter(&idr->idr_lock, RW_WRITER);
+ if (idr->idr_temp == NULL) {
+ idr->idr_temp = temp;
+ temp = NULL;
}
+ rw_exit(&idr->idr_lock);
- new_is->is_n_allocated = (n_used + 1);
-
- membar_producer(); /* match 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 */
- kfree(temp_is->is_data);
- kfree(temp_is);
- }
+ if (temp != NULL)
+ kmem_free(temp, sizeof(*temp));
return 1;
}
int
-idr_get_new_above(struct idr *idr, void *datum, int min_id, int *idp)
+idr_get_new_above(struct idr *idr, void *data, int min_id, int *id)
{
- struct idr_state *is = idr_state(idr);
- const size_t n_used = is->is_n_used;
- const size_t n_allocated = is->is_n_allocated;
- int id;
-
- if (min_id < 0)
- min_id = 0;
-
- for (id = min_id; id < n_used; id++)
- if (is->is_data[id] == NULL)
- goto win;
- if (id < n_allocated) {
- is->is_n_used++;
- goto win;
- }
-
- struct idr_state *const it = atomic_swap_ptr(&idr->idr_temp, NULL);
- if (it == NULL)
- return -EAGAIN;
-
- membar_consumer(); /* match temp */
- if (id < it->is_n_allocated) {
- (void)memcpy(it->is_data, is->is_data, sizeof(void *) *
- n_used);
- it->is_n_used = (is->is_n_used + 1);
- membar_producer(); /* match state */
- idr->idr_state = it;
- pserialize_perform(idr->idr_psz);
- kfree(is->is_data);
- kfree(is);
- is = it;
- goto win;
- }
-
-win: membar_producer(); /* match datum */
- is->is_data[id] = datum;
- *idp = id;
- return 0;
+ struct idr_node *node, *search, *collision __unused;
+ int want_id = min_id;
+ int error;
+
+ rw_enter(&idr->idr_lock, RW_WRITER);
+
+ node = idr->idr_temp;
+ if (node == NULL) {
+ error = -EAGAIN;
+ goto out;
+ }
+ idr->idr_temp = NULL;
+
+ search = rb_tree_find_node_geq(&idr->idr_tree, &min_id);
+ while ((search != NULL) && (search->in_index == want_id)) {
+ if (want_id == INT_MAX) {
+ error = -ENOSPC;
+ goto out;
+ }
+ search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT);
+ want_id++;
+ }
+
+ node->in_index = want_id;
+ node->in_data = data;
+
+ collision = rb_tree_insert_node(&idr->idr_tree, node);
+ KASSERT(collision == node);
+
+ *id = want_id;
+ error = 0;
+
+out: rw_exit(&idr->idr_lock);
+ return error;
}
int
idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg)
{
- struct idr_state *const is = idr_state(idr);
- int id;
+ struct idr_node *node;
int error = 0;
- for (id = 0; id < is->is_n_used; id++) {
- void *const datum = is->is_data[id];
-
- membar_consumer(); /* match datum */
- error = (*proc)(id, datum, arg);
+ rw_enter(&idr->idr_lock, RW_READER);
+ RB_TREE_FOREACH(node, &idr->idr_tree) {
+ error = (*proc)(node->in_index, node->in_data, arg);
if (error)
break;
}
+ rw_exit(&idr->idr_lock);
return error;
}
