Module Name:    src
Committed By:   riastradh
Date:           Mon Dec 30 04:52:11 UTC 2013

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:
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.


To generate a diff of this commit:
cvs rdiff -u -r1.1.2.6 -r1.1.2.7 \
    src/sys/external/bsd/drm2/include/linux/idr.h
cvs rdiff -u -r1.1.2.9 -r1.1.2.10 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.6 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.6	Wed Jul 24 03:13:59 2013
+++ src/sys/external/bsd/drm2/include/linux/idr.h	Mon Dec 30 04:52:11 2013
@@ -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...  */

Index: src/sys/external/bsd/drm2/linux/linux_idr.c
diff -u src/sys/external/bsd/drm2/linux/linux_idr.c:1.1.2.9 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.9	Wed Jul 24 04:02:58 2013
+++ src/sys/external/bsd/drm2/linux/linux_idr.c	Mon Dec 30 04:52:11 2013
@@ -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>
+#include <linux/slab.h>
 
-struct idr_node {
-	rb_node_t in_rb_node;
-	int in_index;
-	void *in_data;
+struct idr_state {
+	size_t			is_n_allocated;
+	size_t			is_n_used;
+	void			**is_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,
-};
-
-static signed int
-idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb)
+void
+idr_init(struct idr *idr)
 {
-	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;
+	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 signed int
-idr_tree_compare_key(void *ctx __unused, const void *n, const void *key)
+static struct idr_state *
+idr_state(struct idr *idr)
 {
-	const int a = ((const struct idr_node *)n)->in_index;
-	const int b = *(const int *)key;
+	struct idr_state *const is = idr->idr_state;
 
-	if (a < b)
-		return -1;
-	else if (b < a)
-		return +1;
-	else
-		return 0;
+	membar_consumer();		/* match state */
+
+	return is;
 }
 
 void
-idr_init(struct idr *idr)
+idr_destroy(struct idr *idr)
 {
+	struct idr_state *const is = idr_state(idr);
 
-	rw_init(&idr->idr_lock);
-	rb_tree_init(&idr->idr_tree, &idr_rb_ops);
-	idr->idr_temp = NULL;
+	kfree(is->is_data);
+	kfree(is);
+	KASSERT(idr->idr_temp == NULL);
+
+	pserialize_destroy(idr->idr_psz);
+	mutex_destroy(&idr->idr_lock);
 }
 
-void
-idr_destroy(struct idr *idr)
+static void **
+idr_find_ptr(struct idr *idr, int id)
 {
+	if (id < 0)
+		return NULL;
 
-	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);
+	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);
 
-	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);
+	if (ptr == NULL)
+		return ERR_PTR(-ENOENT);
+
+	void *const datum = *ptr;
+
+	membar_producer();		/* match datum */
+	*ptr = replacement;
 
-	return result;
+	return datum;
 }
 
 void
 idr_remove(struct idr *idr, int id)
 {
-	struct idr_node *node;
+	if (id < 0)
+		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));
+	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;
+	}
 }
 
 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;
 
-	rw_enter(&idr->idr_lock, RW_WRITER);
-	if (idr->idr_temp == NULL) {
-		idr->idr_temp = temp;
-		temp = NULL;
+	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_exit(&idr->idr_lock);
 
-	if (temp != NULL)
-		kmem_free(temp, sizeof(*temp));
+	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);
+	}
 
 	return 1;
 }
 
 int
-idr_get_new_above(struct idr *idr, void *data, int min_id, int *id)
+idr_get_new_above(struct idr *idr, void *datum, int min_id, int *idp)
 {
-	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;
+	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;
 }
 
 int
 idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg)
 {
-	struct idr_node *node;
+	struct idr_state *const is = idr_state(idr);
+	int id;
 	int error = 0;
 
-	rw_enter(&idr->idr_lock, RW_READER);
-	RB_TREE_FOREACH(node, &idr->idr_tree) {
-		error = (*proc)(node->in_index, node->in_data, arg);
+	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);
 		if (error)
 			break;
 	}
-	rw_exit(&idr->idr_lock);
 
 	return error;
 }

Reply via email to