Home | History | Annotate | Line # | Download | only in linux
linux_idr.c revision 1.1.2.1 
      1 /*	$NetBSD: linux_idr.c,v 1.1.2.1 2013/07/24 00:50:36 riastradh Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2013 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by Taylor R. Campbell.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     29  * POSSIBILITY OF SUCH DAMAGE.
     30  */
     31 
     32 #include <sys/cdefs.h>
     33 __KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.1.2.1 2013/07/24 00:50:36 riastradh Exp $");
     34 
     35 #include <sys/param.h>
     36 #include <sys/atomic.h>
     37 #include <sys/kmem.h>
     38 #include <sys/rbtree.h>
     39 
     40 #include <linux/idr.h>
     41 
     42 struct idr_node {
     43 	rb_node_t in_rb_node;
     44 	int in_index;
     45 	void *in_data;
     46 };
     47 
     48 static signed int idr_tree_compare_nodes(void *, const void *, const void *);
     49 static signed int idr_tree_compare_key(void *, const void *, const void *);
     50 
     51 static const rb_tree_ops_t idr_rb_ops = {
     52 	.rbto_compare_nodes = &idr_tree_compare_nodes,
     53 	.rbto_compare_key = &idr_tree_compare_key,
     54 	.rbto_node_offset = offsetof(struct idr_node, in_rb_node),
     55 	.rbto_context = NULL,
     56 };
     57 
     58 static signed int
     59 idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb)
     60 {
     61 	const int a = ((const struct idr_node *)na)->in_index;
     62 	const int b = ((const struct idr_node *)nb)->in_index;
     63 
     64 	if (a < b)
     65 		return -1;
     66 	else if (b < a)
     67 		 return +1;
     68 	else
     69 		return 0;
     70 }
     71 
     72 static signed int
     73 idr_tree_compare_key(void *ctx __unused, const void *n, const void *key)
     74 {
     75 	const int a = ((const struct idr_node *)n)->in_index;
     76 	const int b = *(const int *)key;
     77 
     78 	if (a < b)
     79 		return -1;
     80 	else if (b < a)
     81 		return +1;
     82 	else
     83 		return 0;
     84 }
     85 
     86 void
     87 idr_init(struct idr *idr)
     88 {
     89 
     90 	rw_init(&idr->idr_lock);
     91 	rb_tree_init(&idr->idr_tree, &idr_rb_ops);
     92 	idr->idr_temp = NULL;
     93 }
     94 
     95 void
     96 idr_destroy(struct idr *idr)
     97 {
     98 
     99 	if (idr->idr_temp != NULL) {
    100 		/* XXX Probably shouldn't happen.  */
    101 		kmem_free(idr->idr_temp, sizeof(*idr->idr_temp));
    102 		idr->idr_temp = NULL;
    103 	}
    104 #if 0				/* XXX No rb_tree_destroy?  */
    105 	rb_tree_destroy(&idr->idr_tree);
    106 #endif
    107 	rw_destroy(&idr->idr_lock);
    108 }
    109 
    110 void *
    111 idr_find(struct idr *idr, int id)
    112 {
    113 	const struct idr_node *node;
    114 	void *data;
    115 
    116 	rw_enter(&idr->idr_lock, RW_READER);
    117 	node = rb_tree_find_node(&idr->idr_tree, &id);
    118 	data = (node == NULL? NULL : node->in_data);
    119 	rw_exit(&idr->idr_lock);
    120 
    121 	return data;
    122 }
    123 
    124 void
    125 idr_remove(struct idr *idr, int id)
    126 {
    127 	struct idr_node *node;
    128 
    129 	rw_enter(&idr->idr_lock, RW_WRITER);
    130 	node = rb_tree_find_node(&idr->idr_tree, &id);
    131 	KASSERT(node != NULL);
    132 	rb_tree_remove_node(&idr->idr_tree, node);
    133 	rw_exit(&idr->idr_lock);
    134 	kmem_free(node, sizeof(*node));
    135 }
    136 
    137 int
    138 idr_pre_get(struct idr *idr, int flags __unused /* XXX */)
    139 {
    140 	struct idr_node *const temp = kmem_alloc(sizeof(*temp), KM_SLEEP);
    141 
    142 	if (temp == NULL)
    143 		return 0;
    144 
    145 	if (atomic_cas_ptr(&idr->idr_temp, NULL, temp) != NULL)
    146 		kmem_free(temp, sizeof(*temp));
    147 
    148 	return 1;
    149 }
    150 
    151 int
    152 idr_get_new_above(struct idr *idr, void *data, int min_id, int *id)
    153 {
    154 	struct idr_node *node, *search, *collision __unused;
    155 	int want_id = min_id;
    156 
    157 	node = atomic_swap_ptr(&idr->idr_temp, NULL);
    158 	if (node == NULL)
    159 		return -EAGAIN;
    160 
    161 	rw_enter(&idr->idr_lock, RW_WRITER);
    162 
    163 	search = rb_tree_find_node_geq(&idr->idr_tree, &min_id);
    164 	while ((search != NULL) && (search->in_index == want_id)) {
    165 		search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT);
    166 		want_id++;
    167 	}
    168 
    169 	node->in_index = want_id;
    170 	node->in_data = data;
    171 
    172 	collision = rb_tree_insert_node(&idr->idr_tree, node);
    173 	KASSERT(collision == node);
    174 
    175 	rw_exit(&idr->idr_lock);
    176 
    177 	return 0;
    178 }
    179