Home | History | Annotate | Line # | Download | only in linux
linux_idr.c revision 1.7
      1 /*	$NetBSD: linux_idr.c,v 1.7 2018/08/27 06:55:01 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.7 2018/08/27 06:55:01 riastradh Exp $");
     34 
     35 #include <sys/param.h>
     36 #include <sys/atomic.h>
     37 #include <sys/rbtree.h>
     38 
     39 #include <linux/err.h>
     40 #include <linux/idr.h>
     41 #include <linux/slab.h>
     42 
     43 struct idr_node {
     44 	rb_node_t		in_rb_node;
     45 	int			in_index;
     46 	void			*in_data;
     47 	SIMPLEQ_ENTRY(idr_node)	in_list;
     48 };
     49 SIMPLEQ_HEAD(idr_head, idr_node);
     50 
     51 static struct {
     52 	kmutex_t	lock;
     53 	struct idr_head	preloaded_nodes;
     54 	struct idr_head	discarded_nodes;
     55 } idr_cache __cacheline_aligned;
     56 
     57 int
     58 linux_idr_module_init(void)
     59 {
     60 
     61 	mutex_init(&idr_cache.lock, MUTEX_DEFAULT, IPL_VM);
     62 	SIMPLEQ_INIT(&idr_cache.preloaded_nodes);
     63 	SIMPLEQ_INIT(&idr_cache.discarded_nodes);
     64 	return 0;
     65 }
     66 
     67 void
     68 linux_idr_module_fini(void)
     69 {
     70 
     71 	KASSERT(SIMPLEQ_EMPTY(&idr_cache.discarded_nodes));
     72 	KASSERT(SIMPLEQ_EMPTY(&idr_cache.preloaded_nodes));
     73 	mutex_destroy(&idr_cache.lock);
     74 }
     75 
     76 static signed int idr_tree_compare_nodes(void *, const void *, const void *);
     77 static signed int idr_tree_compare_key(void *, const void *, const void *);
     78 
     79 static const rb_tree_ops_t idr_rb_ops = {
     80 	.rbto_compare_nodes = &idr_tree_compare_nodes,
     81 	.rbto_compare_key = &idr_tree_compare_key,
     82 	.rbto_node_offset = offsetof(struct idr_node, in_rb_node),
     83 	.rbto_context = NULL,
     84 };
     85 
     86 static signed int
     87 idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb)
     88 {
     89 	const int a = ((const struct idr_node *)na)->in_index;
     90 	const int b = ((const struct idr_node *)nb)->in_index;
     91 
     92 	if (a < b)
     93 		return -1;
     94 	else if (b < a)
     95 		 return +1;
     96 	else
     97 		return 0;
     98 }
     99 
    100 static signed int
    101 idr_tree_compare_key(void *ctx __unused, const void *n, const void *key)
    102 {
    103 	const int a = ((const struct idr_node *)n)->in_index;
    104 	const int b = *(const int *)key;
    105 
    106 	if (a < b)
    107 		return -1;
    108 	else if (b < a)
    109 		return +1;
    110 	else
    111 		return 0;
    112 }
    113 
    114 void
    115 idr_init(struct idr *idr)
    116 {
    117 
    118 	mutex_init(&idr->idr_lock, MUTEX_DEFAULT, IPL_VM);
    119 	rb_tree_init(&idr->idr_tree, &idr_rb_ops);
    120 }
    121 
    122 void
    123 idr_destroy(struct idr *idr)
    124 {
    125 
    126 #if 0				/* XXX No rb_tree_destroy?  */
    127 	rb_tree_destroy(&idr->idr_tree);
    128 #endif
    129 	mutex_destroy(&idr->idr_lock);
    130 }
    131 
    132 bool
    133 idr_is_empty(struct idr *idr)
    134 {
    135 
    136 	return (RB_TREE_MIN(&idr->idr_tree) == NULL);
    137 }
    138 
    139 void *
    140 idr_find(struct idr *idr, int id)
    141 {
    142 	const struct idr_node *node;
    143 	void *data;
    144 
    145 	mutex_spin_enter(&idr->idr_lock);
    146 	node = rb_tree_find_node(&idr->idr_tree, &id);
    147 	data = (node == NULL? NULL : node->in_data);
    148 	mutex_spin_exit(&idr->idr_lock);
    149 
    150 	return data;
    151 }
    152 
    153 void *
    154 idr_get_next(struct idr *idr, int *idp)
    155 {
    156 	const struct idr_node *node;
    157 	void *data;
    158 
    159 	mutex_spin_enter(&idr->idr_lock);
    160 	node = rb_tree_find_node_geq(&idr->idr_tree, idp);
    161 	if (node == NULL) {
    162 		data = NULL;
    163 	} else {
    164 		data = node->in_data;
    165 		*idp = node->in_index;
    166 	}
    167 	mutex_spin_exit(&idr->idr_lock);
    168 
    169 	return data;
    170 }
    171 
    172 void *
    173 idr_replace(struct idr *idr, void *replacement, int id)
    174 {
    175 	struct idr_node *node;
    176 	void *result;
    177 
    178 	mutex_spin_enter(&idr->idr_lock);
    179 	node = rb_tree_find_node(&idr->idr_tree, &id);
    180 	if (node == NULL) {
    181 		result = ERR_PTR(-ENOENT);
    182 	} else {
    183 		result = node->in_data;
    184 		node->in_data = replacement;
    185 	}
    186 	mutex_spin_exit(&idr->idr_lock);
    187 
    188 	return result;
    189 }
    190 
    191 void
    192 idr_remove(struct idr *idr, int id)
    193 {
    194 	struct idr_node *node;
    195 
    196 	mutex_spin_enter(&idr->idr_lock);
    197 	node = rb_tree_find_node(&idr->idr_tree, &id);
    198 	KASSERTMSG((node != NULL), "idr %p has no entry for id %d", idr, id);
    199 	rb_tree_remove_node(&idr->idr_tree, node);
    200 	mutex_spin_exit(&idr->idr_lock);
    201 	kfree(node);
    202 }
    203 
    204 void
    205 idr_preload(gfp_t gfp)
    206 {
    207 	struct idr_node *node;
    208 
    209 	if (ISSET(gfp, __GFP_WAIT))
    210 		ASSERT_SLEEPABLE();
    211 
    212 	node = kmalloc(sizeof(*node), gfp);
    213 	KASSERT(node != NULL || !ISSET(gfp, __GFP_WAIT));
    214 	if (node == NULL)
    215 		return;
    216 
    217 	mutex_spin_enter(&idr_cache.lock);
    218 	SIMPLEQ_INSERT_TAIL(&idr_cache.preloaded_nodes, node, in_list);
    219 	mutex_spin_exit(&idr_cache.lock);
    220 }
    221 
    222 int
    223 idr_alloc(struct idr *idr, void *data, int start, int end, gfp_t gfp)
    224 {
    225 	int maximum = (end <= 0? INT_MAX : (end - 1));
    226 	struct idr_node *node, *search, *collision __diagused;
    227 	int id = start;
    228 
    229 	/* Sanity-check inputs.  */
    230 	if (ISSET(gfp, __GFP_WAIT))
    231 		ASSERT_SLEEPABLE();
    232 	if (__predict_false(start < 0))
    233 		return -EINVAL;
    234 	if (__predict_false(maximum < start))
    235 		return -ENOSPC;
    236 
    237 	/* Grab a node allocated by idr_preload.  */
    238 	mutex_spin_enter(&idr_cache.lock);
    239 	if (SIMPLEQ_EMPTY(&idr_cache.preloaded_nodes)) {
    240 		mutex_spin_exit(&idr_cache.lock);
    241 		return -ENOMEM;
    242 	}
    243 	node = SIMPLEQ_FIRST(&idr_cache.preloaded_nodes);
    244 	SIMPLEQ_REMOVE_HEAD(&idr_cache.preloaded_nodes, in_list);
    245 	mutex_spin_exit(&idr_cache.lock);
    246 
    247 	/* Find an id.  */
    248 	mutex_spin_enter(&idr->idr_lock);
    249 	search = rb_tree_find_node_geq(&idr->idr_tree, &start);
    250 	while ((search != NULL) && (search->in_index == id)) {
    251 		if (maximum <= id) {
    252 			id = -ENOSPC;
    253 			goto out;
    254 		}
    255 		search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT);
    256 		id++;
    257 	}
    258 	node->in_index = id;
    259 	node->in_data = data;
    260 	collision = rb_tree_insert_node(&idr->idr_tree, node);
    261 	KASSERT(collision == node);
    262 out:	mutex_spin_exit(&idr->idr_lock);
    263 
    264 	if (id < 0) {
    265 		/* Discard the node on failure.  */
    266 		mutex_spin_enter(&idr_cache.lock);
    267 		SIMPLEQ_INSERT_HEAD(&idr_cache.discarded_nodes, node, in_list);
    268 		mutex_spin_exit(&idr_cache.lock);
    269 	}
    270 	return id;
    271 }
    272 
    273 void
    274 idr_preload_end(void)
    275 {
    276 	struct idr_head temp = SIMPLEQ_HEAD_INITIALIZER(temp);
    277 	struct idr_node *node, *next;
    278 
    279 	mutex_spin_enter(&idr_cache.lock);
    280 	SIMPLEQ_FOREACH_SAFE(node, &idr_cache.discarded_nodes, in_list, next) {
    281 		SIMPLEQ_REMOVE_HEAD(&idr_cache.discarded_nodes, in_list);
    282 		SIMPLEQ_INSERT_HEAD(&temp, node, in_list);
    283 	}
    284 	mutex_spin_exit(&idr_cache.lock);
    285 
    286 	SIMPLEQ_FOREACH_SAFE(node, &temp, in_list, next) {
    287 		SIMPLEQ_REMOVE_HEAD(&temp, in_list);
    288 		kfree(node);
    289 	}
    290 }
    291 
    292 int
    293 idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg)
    294 {
    295 	struct idr_node *node;
    296 	int error = 0;
    297 
    298 	/* XXX Caller must exclude modifications.  */
    299 	membar_consumer();
    300 	RB_TREE_FOREACH(node, &idr->idr_tree) {
    301 		error = (*proc)(node->in_index, node->in_data, arg);
    302 		if (error)
    303 			break;
    304 	}
    305 
    306 	return error;
    307 }
    308