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; }