linux_idr.c revision 1.2.2.1
1 1.2.2.1 tls /* $NetBSD: linux_idr.c,v 1.2.2.1 2014/08/10 06:55:40 tls Exp $ */ 2 1.2 riastrad 3 1.2 riastrad /*- 4 1.2 riastrad * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 1.2 riastrad * All rights reserved. 6 1.2 riastrad * 7 1.2 riastrad * This code is derived from software contributed to The NetBSD Foundation 8 1.2 riastrad * by Taylor R. Campbell. 9 1.2 riastrad * 10 1.2 riastrad * Redistribution and use in source and binary forms, with or without 11 1.2 riastrad * modification, are permitted provided that the following conditions 12 1.2 riastrad * are met: 13 1.2 riastrad * 1. Redistributions of source code must retain the above copyright 14 1.2 riastrad * notice, this list of conditions and the following disclaimer. 15 1.2 riastrad * 2. Redistributions in binary form must reproduce the above copyright 16 1.2 riastrad * notice, this list of conditions and the following disclaimer in the 17 1.2 riastrad * documentation and/or other materials provided with the distribution. 18 1.2 riastrad * 19 1.2 riastrad * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 1.2 riastrad * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 1.2 riastrad * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 1.2 riastrad * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 1.2 riastrad * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 1.2 riastrad * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 1.2 riastrad * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 1.2 riastrad * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 1.2 riastrad * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 1.2 riastrad * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 1.2 riastrad * POSSIBILITY OF SUCH DAMAGE. 30 1.2 riastrad */ 31 1.2 riastrad 32 1.2 riastrad #include <sys/cdefs.h> 33 1.2.2.1 tls __KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.2.2.1 2014/08/10 06:55:40 tls Exp $"); 34 1.2 riastrad 35 1.2 riastrad #include <sys/param.h> 36 1.2 riastrad #include <sys/atomic.h> 37 1.2 riastrad #include <sys/rbtree.h> 38 1.2 riastrad 39 1.2 riastrad #include <linux/err.h> 40 1.2 riastrad #include <linux/idr.h> 41 1.2.2.1 tls #include <linux/slab.h> 42 1.2 riastrad 43 1.2 riastrad struct idr_node { 44 1.2.2.1 tls rb_node_t in_rb_node; 45 1.2.2.1 tls int in_index; 46 1.2.2.1 tls void *in_data; 47 1.2.2.1 tls SIMPLEQ_ENTRY(idr_node) in_list; 48 1.2 riastrad }; 49 1.2.2.1 tls SIMPLEQ_HEAD(idr_head, idr_node); 50 1.2.2.1 tls 51 1.2.2.1 tls static struct { 52 1.2.2.1 tls kmutex_t lock; 53 1.2.2.1 tls struct idr_head preloaded_nodes; 54 1.2.2.1 tls struct idr_head discarded_nodes; 55 1.2.2.1 tls } idr_cache __cacheline_aligned; 56 1.2.2.1 tls 57 1.2.2.1 tls int 58 1.2.2.1 tls linux_idr_module_init(void) 59 1.2.2.1 tls { 60 1.2.2.1 tls 61 1.2.2.1 tls mutex_init(&idr_cache.lock, MUTEX_DEFAULT, IPL_VM); 62 1.2.2.1 tls SIMPLEQ_INIT(&idr_cache.preloaded_nodes); 63 1.2.2.1 tls SIMPLEQ_INIT(&idr_cache.discarded_nodes); 64 1.2.2.1 tls return 0; 65 1.2.2.1 tls } 66 1.2.2.1 tls 67 1.2.2.1 tls void 68 1.2.2.1 tls linux_idr_module_fini(void) 69 1.2.2.1 tls { 70 1.2.2.1 tls 71 1.2.2.1 tls KASSERT(SIMPLEQ_EMPTY(&idr_cache.discarded_nodes)); 72 1.2.2.1 tls KASSERT(SIMPLEQ_EMPTY(&idr_cache.preloaded_nodes)); 73 1.2.2.1 tls mutex_destroy(&idr_cache.lock); 74 1.2.2.1 tls } 75 1.2 riastrad 76 1.2 riastrad static signed int idr_tree_compare_nodes(void *, const void *, const void *); 77 1.2 riastrad static signed int idr_tree_compare_key(void *, const void *, const void *); 78 1.2 riastrad 79 1.2 riastrad static const rb_tree_ops_t idr_rb_ops = { 80 1.2 riastrad .rbto_compare_nodes = &idr_tree_compare_nodes, 81 1.2 riastrad .rbto_compare_key = &idr_tree_compare_key, 82 1.2 riastrad .rbto_node_offset = offsetof(struct idr_node, in_rb_node), 83 1.2 riastrad .rbto_context = NULL, 84 1.2 riastrad }; 85 1.2 riastrad 86 1.2 riastrad static signed int 87 1.2 riastrad idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb) 88 1.2 riastrad { 89 1.2 riastrad const int a = ((const struct idr_node *)na)->in_index; 90 1.2 riastrad const int b = ((const struct idr_node *)nb)->in_index; 91 1.2 riastrad 92 1.2 riastrad if (a < b) 93 1.2 riastrad return -1; 94 1.2 riastrad else if (b < a) 95 1.2 riastrad return +1; 96 1.2 riastrad else 97 1.2 riastrad return 0; 98 1.2 riastrad } 99 1.2 riastrad 100 1.2 riastrad static signed int 101 1.2 riastrad idr_tree_compare_key(void *ctx __unused, const void *n, const void *key) 102 1.2 riastrad { 103 1.2 riastrad const int a = ((const struct idr_node *)n)->in_index; 104 1.2 riastrad const int b = *(const int *)key; 105 1.2 riastrad 106 1.2 riastrad if (a < b) 107 1.2 riastrad return -1; 108 1.2 riastrad else if (b < a) 109 1.2 riastrad return +1; 110 1.2 riastrad else 111 1.2 riastrad return 0; 112 1.2 riastrad } 113 1.2 riastrad 114 1.2 riastrad void 115 1.2 riastrad idr_init(struct idr *idr) 116 1.2 riastrad { 117 1.2 riastrad 118 1.2 riastrad mutex_init(&idr->idr_lock, MUTEX_DEFAULT, IPL_VM); 119 1.2 riastrad rb_tree_init(&idr->idr_tree, &idr_rb_ops); 120 1.2 riastrad } 121 1.2 riastrad 122 1.2 riastrad void 123 1.2 riastrad idr_destroy(struct idr *idr) 124 1.2 riastrad { 125 1.2 riastrad 126 1.2 riastrad #if 0 /* XXX No rb_tree_destroy? */ 127 1.2 riastrad rb_tree_destroy(&idr->idr_tree); 128 1.2 riastrad #endif 129 1.2 riastrad mutex_destroy(&idr->idr_lock); 130 1.2 riastrad } 131 1.2 riastrad 132 1.2.2.1 tls bool 133 1.2.2.1 tls idr_is_empty(struct idr *idr) 134 1.2.2.1 tls { 135 1.2.2.1 tls 136 1.2.2.1 tls return (RB_TREE_MIN(&idr->idr_tree) == NULL); 137 1.2.2.1 tls } 138 1.2.2.1 tls 139 1.2 riastrad void * 140 1.2 riastrad idr_find(struct idr *idr, int id) 141 1.2 riastrad { 142 1.2 riastrad const struct idr_node *node; 143 1.2 riastrad void *data; 144 1.2 riastrad 145 1.2 riastrad mutex_spin_enter(&idr->idr_lock); 146 1.2 riastrad node = rb_tree_find_node(&idr->idr_tree, &id); 147 1.2 riastrad data = (node == NULL? NULL : node->in_data); 148 1.2 riastrad mutex_spin_exit(&idr->idr_lock); 149 1.2 riastrad 150 1.2 riastrad return data; 151 1.2 riastrad } 152 1.2 riastrad 153 1.2 riastrad void * 154 1.2 riastrad idr_replace(struct idr *idr, void *replacement, int id) 155 1.2 riastrad { 156 1.2 riastrad struct idr_node *node; 157 1.2 riastrad void *result; 158 1.2 riastrad 159 1.2 riastrad mutex_spin_enter(&idr->idr_lock); 160 1.2 riastrad node = rb_tree_find_node(&idr->idr_tree, &id); 161 1.2 riastrad if (node == NULL) { 162 1.2 riastrad result = ERR_PTR(-ENOENT); 163 1.2 riastrad } else { 164 1.2 riastrad result = node->in_data; 165 1.2 riastrad node->in_data = replacement; 166 1.2 riastrad } 167 1.2 riastrad mutex_spin_exit(&idr->idr_lock); 168 1.2 riastrad 169 1.2 riastrad return result; 170 1.2 riastrad } 171 1.2 riastrad 172 1.2 riastrad void 173 1.2 riastrad idr_remove(struct idr *idr, int id) 174 1.2 riastrad { 175 1.2 riastrad struct idr_node *node; 176 1.2 riastrad 177 1.2 riastrad mutex_spin_enter(&idr->idr_lock); 178 1.2 riastrad node = rb_tree_find_node(&idr->idr_tree, &id); 179 1.2.2.1 tls KASSERTMSG((node != NULL), "idr %p has no entry for id %d", idr, id); 180 1.2 riastrad rb_tree_remove_node(&idr->idr_tree, node); 181 1.2 riastrad mutex_spin_exit(&idr->idr_lock); 182 1.2.2.1 tls kfree(node); 183 1.2 riastrad } 184 1.2 riastrad 185 1.2 riastrad void 186 1.2.2.1 tls idr_preload(gfp_t gfp) 187 1.2 riastrad { 188 1.2 riastrad struct idr_node *node; 189 1.2 riastrad 190 1.2.2.1 tls if (ISSET(gfp, __GFP_WAIT)) 191 1.2.2.1 tls ASSERT_SLEEPABLE(); 192 1.2 riastrad 193 1.2.2.1 tls node = kmalloc(sizeof(*node), gfp); 194 1.2.2.1 tls if (node == NULL) 195 1.2.2.1 tls return; 196 1.2.2.1 tls 197 1.2.2.1 tls mutex_spin_enter(&idr_cache.lock); 198 1.2.2.1 tls SIMPLEQ_INSERT_TAIL(&idr_cache.preloaded_nodes, node, in_list); 199 1.2.2.1 tls mutex_spin_exit(&idr_cache.lock); 200 1.2 riastrad } 201 1.2 riastrad 202 1.2 riastrad int 203 1.2.2.1 tls idr_alloc(struct idr *idr, void *data, int start, int end, gfp_t gfp) 204 1.2 riastrad { 205 1.2.2.1 tls int maximum = (end <= 0? INT_MAX : (end - 1)); 206 1.2.2.1 tls struct idr_node *node, *search, *collision __diagused; 207 1.2.2.1 tls int id = start; 208 1.2.2.1 tls 209 1.2.2.1 tls /* Sanity-check inputs. */ 210 1.2.2.1 tls if (ISSET(gfp, __GFP_WAIT)) 211 1.2.2.1 tls ASSERT_SLEEPABLE(); 212 1.2.2.1 tls if (__predict_false(start < 0)) 213 1.2.2.1 tls return -EINVAL; 214 1.2.2.1 tls if (__predict_false(maximum < start)) 215 1.2.2.1 tls return -ENOSPC; 216 1.2.2.1 tls 217 1.2.2.1 tls /* Grab a node allocated by idr_preload. */ 218 1.2.2.1 tls mutex_spin_enter(&idr_cache.lock); 219 1.2.2.1 tls KASSERTMSG(!SIMPLEQ_EMPTY(&idr_cache.preloaded_nodes), 220 1.2.2.1 tls "missing call to idr_preload"); 221 1.2.2.1 tls node = SIMPLEQ_FIRST(&idr_cache.preloaded_nodes); 222 1.2.2.1 tls SIMPLEQ_REMOVE_HEAD(&idr_cache.preloaded_nodes, in_list); 223 1.2.2.1 tls mutex_spin_exit(&idr_cache.lock); 224 1.2 riastrad 225 1.2.2.1 tls /* Find an id. */ 226 1.2 riastrad mutex_spin_enter(&idr->idr_lock); 227 1.2.2.1 tls search = rb_tree_find_node_geq(&idr->idr_tree, &start); 228 1.2.2.1 tls while ((search != NULL) && (search->in_index == id)) { 229 1.2.2.1 tls if (maximum <= id) { 230 1.2.2.1 tls id = -ENOSPC; 231 1.2 riastrad goto out; 232 1.2 riastrad } 233 1.2 riastrad search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT); 234 1.2.2.1 tls id++; 235 1.2 riastrad } 236 1.2.2.1 tls node->in_index = id; 237 1.2 riastrad node->in_data = data; 238 1.2 riastrad collision = rb_tree_insert_node(&idr->idr_tree, node); 239 1.2 riastrad KASSERT(collision == node); 240 1.2.2.1 tls out: mutex_spin_exit(&idr->idr_lock); 241 1.2 riastrad 242 1.2.2.1 tls if (id < 0) { 243 1.2.2.1 tls /* Discard the node on failure. */ 244 1.2.2.1 tls mutex_spin_enter(&idr_cache.lock); 245 1.2.2.1 tls SIMPLEQ_INSERT_HEAD(&idr_cache.discarded_nodes, node, in_list); 246 1.2.2.1 tls mutex_spin_exit(&idr_cache.lock); 247 1.2.2.1 tls } 248 1.2.2.1 tls return id; 249 1.2.2.1 tls } 250 1.2 riastrad 251 1.2.2.1 tls void 252 1.2.2.1 tls idr_preload_end(void) 253 1.2.2.1 tls { 254 1.2.2.1 tls struct idr_head temp = SIMPLEQ_HEAD_INITIALIZER(temp); 255 1.2.2.1 tls struct idr_node *node, *next; 256 1.2.2.1 tls 257 1.2.2.1 tls mutex_spin_enter(&idr_cache.lock); 258 1.2.2.1 tls SIMPLEQ_FOREACH_SAFE(node, &idr_cache.discarded_nodes, in_list, next) { 259 1.2.2.1 tls SIMPLEQ_REMOVE_HEAD(&idr_cache.discarded_nodes, in_list); 260 1.2.2.1 tls SIMPLEQ_INSERT_HEAD(&temp, node, in_list); 261 1.2.2.1 tls } 262 1.2.2.1 tls mutex_spin_exit(&idr_cache.lock); 263 1.2.2.1 tls 264 1.2.2.1 tls SIMPLEQ_FOREACH_SAFE(node, &temp, in_list, next) { 265 1.2.2.1 tls SIMPLEQ_REMOVE_HEAD(&temp, in_list); 266 1.2.2.1 tls kfree(node); 267 1.2.2.1 tls } 268 1.2 riastrad } 269 1.2 riastrad 270 1.2 riastrad int 271 1.2 riastrad idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg) 272 1.2 riastrad { 273 1.2 riastrad struct idr_node *node; 274 1.2 riastrad int error = 0; 275 1.2 riastrad 276 1.2 riastrad /* XXX Caller must exclude modifications. */ 277 1.2 riastrad membar_consumer(); 278 1.2 riastrad RB_TREE_FOREACH(node, &idr->idr_tree) { 279 1.2 riastrad error = (*proc)(node->in_index, node->in_data, arg); 280 1.2 riastrad if (error) 281 1.2 riastrad break; 282 1.2 riastrad } 283 1.2 riastrad 284 1.2 riastrad return error; 285 1.2 riastrad } 286
Indexes created Tue Sep 30 11:09:46 GMT 2025