linux_idr.c revision 1.2.4.2
1 1.2.4.2 rmind /* $NetBSD: linux_idr.c,v 1.2.4.2 2014/05/18 17:46:01 rmind Exp $ */ 2 1.2.4.2 rmind 3 1.2.4.2 rmind /*- 4 1.2.4.2 rmind * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 1.2.4.2 rmind * All rights reserved. 6 1.2.4.2 rmind * 7 1.2.4.2 rmind * This code is derived from software contributed to The NetBSD Foundation 8 1.2.4.2 rmind * by Taylor R. Campbell. 9 1.2.4.2 rmind * 10 1.2.4.2 rmind * Redistribution and use in source and binary forms, with or without 11 1.2.4.2 rmind * modification, are permitted provided that the following conditions 12 1.2.4.2 rmind * are met: 13 1.2.4.2 rmind * 1. Redistributions of source code must retain the above copyright 14 1.2.4.2 rmind * notice, this list of conditions and the following disclaimer. 15 1.2.4.2 rmind * 2. Redistributions in binary form must reproduce the above copyright 16 1.2.4.2 rmind * notice, this list of conditions and the following disclaimer in the 17 1.2.4.2 rmind * documentation and/or other materials provided with the distribution. 18 1.2.4.2 rmind * 19 1.2.4.2 rmind * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 1.2.4.2 rmind * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 1.2.4.2 rmind * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 1.2.4.2 rmind * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 1.2.4.2 rmind * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 1.2.4.2 rmind * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 1.2.4.2 rmind * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 1.2.4.2 rmind * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 1.2.4.2 rmind * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 1.2.4.2 rmind * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 1.2.4.2 rmind * POSSIBILITY OF SUCH DAMAGE. 30 1.2.4.2 rmind */ 31 1.2.4.2 rmind 32 1.2.4.2 rmind #include <sys/cdefs.h> 33 1.2.4.2 rmind __KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.2.4.2 2014/05/18 17:46:01 rmind Exp $"); 34 1.2.4.2 rmind 35 1.2.4.2 rmind #include <sys/param.h> 36 1.2.4.2 rmind #include <sys/atomic.h> 37 1.2.4.2 rmind #include <sys/kmem.h> 38 1.2.4.2 rmind #include <sys/rbtree.h> 39 1.2.4.2 rmind 40 1.2.4.2 rmind #include <linux/err.h> 41 1.2.4.2 rmind #include <linux/idr.h> 42 1.2.4.2 rmind 43 1.2.4.2 rmind struct idr_node { 44 1.2.4.2 rmind rb_node_t in_rb_node; 45 1.2.4.2 rmind int in_index; 46 1.2.4.2 rmind void *in_data; 47 1.2.4.2 rmind }; 48 1.2.4.2 rmind 49 1.2.4.2 rmind static signed int idr_tree_compare_nodes(void *, const void *, const void *); 50 1.2.4.2 rmind static signed int idr_tree_compare_key(void *, const void *, const void *); 51 1.2.4.2 rmind 52 1.2.4.2 rmind static const rb_tree_ops_t idr_rb_ops = { 53 1.2.4.2 rmind .rbto_compare_nodes = &idr_tree_compare_nodes, 54 1.2.4.2 rmind .rbto_compare_key = &idr_tree_compare_key, 55 1.2.4.2 rmind .rbto_node_offset = offsetof(struct idr_node, in_rb_node), 56 1.2.4.2 rmind .rbto_context = NULL, 57 1.2.4.2 rmind }; 58 1.2.4.2 rmind 59 1.2.4.2 rmind static signed int 60 1.2.4.2 rmind idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb) 61 1.2.4.2 rmind { 62 1.2.4.2 rmind const int a = ((const struct idr_node *)na)->in_index; 63 1.2.4.2 rmind const int b = ((const struct idr_node *)nb)->in_index; 64 1.2.4.2 rmind 65 1.2.4.2 rmind if (a < b) 66 1.2.4.2 rmind return -1; 67 1.2.4.2 rmind else if (b < a) 68 1.2.4.2 rmind return +1; 69 1.2.4.2 rmind else 70 1.2.4.2 rmind return 0; 71 1.2.4.2 rmind } 72 1.2.4.2 rmind 73 1.2.4.2 rmind static signed int 74 1.2.4.2 rmind idr_tree_compare_key(void *ctx __unused, const void *n, const void *key) 75 1.2.4.2 rmind { 76 1.2.4.2 rmind const int a = ((const struct idr_node *)n)->in_index; 77 1.2.4.2 rmind const int b = *(const int *)key; 78 1.2.4.2 rmind 79 1.2.4.2 rmind if (a < b) 80 1.2.4.2 rmind return -1; 81 1.2.4.2 rmind else if (b < a) 82 1.2.4.2 rmind return +1; 83 1.2.4.2 rmind else 84 1.2.4.2 rmind return 0; 85 1.2.4.2 rmind } 86 1.2.4.2 rmind 87 1.2.4.2 rmind void 88 1.2.4.2 rmind idr_init(struct idr *idr) 89 1.2.4.2 rmind { 90 1.2.4.2 rmind 91 1.2.4.2 rmind mutex_init(&idr->idr_lock, MUTEX_DEFAULT, IPL_VM); 92 1.2.4.2 rmind rb_tree_init(&idr->idr_tree, &idr_rb_ops); 93 1.2.4.2 rmind idr->idr_temp = NULL; 94 1.2.4.2 rmind } 95 1.2.4.2 rmind 96 1.2.4.2 rmind void 97 1.2.4.2 rmind idr_destroy(struct idr *idr) 98 1.2.4.2 rmind { 99 1.2.4.2 rmind 100 1.2.4.2 rmind if (idr->idr_temp != NULL) { 101 1.2.4.2 rmind /* XXX Probably shouldn't happen. */ 102 1.2.4.2 rmind kmem_free(idr->idr_temp, sizeof(*idr->idr_temp)); 103 1.2.4.2 rmind idr->idr_temp = NULL; 104 1.2.4.2 rmind } 105 1.2.4.2 rmind #if 0 /* XXX No rb_tree_destroy? */ 106 1.2.4.2 rmind rb_tree_destroy(&idr->idr_tree); 107 1.2.4.2 rmind #endif 108 1.2.4.2 rmind mutex_destroy(&idr->idr_lock); 109 1.2.4.2 rmind } 110 1.2.4.2 rmind 111 1.2.4.2 rmind void * 112 1.2.4.2 rmind idr_find(struct idr *idr, int id) 113 1.2.4.2 rmind { 114 1.2.4.2 rmind const struct idr_node *node; 115 1.2.4.2 rmind void *data; 116 1.2.4.2 rmind 117 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 118 1.2.4.2 rmind node = rb_tree_find_node(&idr->idr_tree, &id); 119 1.2.4.2 rmind data = (node == NULL? NULL : node->in_data); 120 1.2.4.2 rmind mutex_spin_exit(&idr->idr_lock); 121 1.2.4.2 rmind 122 1.2.4.2 rmind return data; 123 1.2.4.2 rmind } 124 1.2.4.2 rmind 125 1.2.4.2 rmind void * 126 1.2.4.2 rmind idr_replace(struct idr *idr, void *replacement, int id) 127 1.2.4.2 rmind { 128 1.2.4.2 rmind struct idr_node *node; 129 1.2.4.2 rmind void *result; 130 1.2.4.2 rmind 131 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 132 1.2.4.2 rmind node = rb_tree_find_node(&idr->idr_tree, &id); 133 1.2.4.2 rmind if (node == NULL) { 134 1.2.4.2 rmind result = ERR_PTR(-ENOENT); 135 1.2.4.2 rmind } else { 136 1.2.4.2 rmind result = node->in_data; 137 1.2.4.2 rmind node->in_data = replacement; 138 1.2.4.2 rmind } 139 1.2.4.2 rmind mutex_spin_exit(&idr->idr_lock); 140 1.2.4.2 rmind 141 1.2.4.2 rmind return result; 142 1.2.4.2 rmind } 143 1.2.4.2 rmind 144 1.2.4.2 rmind void 145 1.2.4.2 rmind idr_remove(struct idr *idr, int id) 146 1.2.4.2 rmind { 147 1.2.4.2 rmind struct idr_node *node; 148 1.2.4.2 rmind 149 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 150 1.2.4.2 rmind node = rb_tree_find_node(&idr->idr_tree, &id); 151 1.2.4.2 rmind KASSERT(node != NULL); 152 1.2.4.2 rmind rb_tree_remove_node(&idr->idr_tree, node); 153 1.2.4.2 rmind mutex_spin_exit(&idr->idr_lock); 154 1.2.4.2 rmind kmem_free(node, sizeof(*node)); 155 1.2.4.2 rmind } 156 1.2.4.2 rmind 157 1.2.4.2 rmind void 158 1.2.4.2 rmind idr_remove_all(struct idr *idr) 159 1.2.4.2 rmind { 160 1.2.4.2 rmind struct idr_node *node; 161 1.2.4.2 rmind 162 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 163 1.2.4.2 rmind while ((node = RB_TREE_MIN(&idr->idr_tree)) != NULL) { 164 1.2.4.2 rmind rb_tree_remove_node(&idr->idr_tree, node); 165 1.2.4.2 rmind mutex_spin_exit(&idr->idr_lock); 166 1.2.4.2 rmind kmem_free(node, sizeof(*node)); 167 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 168 1.2.4.2 rmind } 169 1.2.4.2 rmind mutex_spin_exit(&idr->idr_lock); 170 1.2.4.2 rmind } 171 1.2.4.2 rmind 172 1.2.4.2 rmind int 173 1.2.4.2 rmind idr_pre_get(struct idr *idr, int flags __unused /* XXX */) 174 1.2.4.2 rmind { 175 1.2.4.2 rmind struct idr_node *temp = kmem_alloc(sizeof(*temp), KM_SLEEP); 176 1.2.4.2 rmind 177 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 178 1.2.4.2 rmind if (idr->idr_temp == NULL) { 179 1.2.4.2 rmind idr->idr_temp = temp; 180 1.2.4.2 rmind temp = NULL; 181 1.2.4.2 rmind } 182 1.2.4.2 rmind mutex_spin_exit(&idr->idr_lock); 183 1.2.4.2 rmind 184 1.2.4.2 rmind if (temp != NULL) 185 1.2.4.2 rmind kmem_free(temp, sizeof(*temp)); 186 1.2.4.2 rmind 187 1.2.4.2 rmind return 1; 188 1.2.4.2 rmind } 189 1.2.4.2 rmind 190 1.2.4.2 rmind int 191 1.2.4.2 rmind idr_get_new_above(struct idr *idr, void *data, int min_id, int *id) 192 1.2.4.2 rmind { 193 1.2.4.2 rmind struct idr_node *node, *search, *collision __unused; 194 1.2.4.2 rmind int want_id = min_id; 195 1.2.4.2 rmind int error; 196 1.2.4.2 rmind 197 1.2.4.2 rmind mutex_spin_enter(&idr->idr_lock); 198 1.2.4.2 rmind 199 1.2.4.2 rmind node = idr->idr_temp; 200 1.2.4.2 rmind if (node == NULL) { 201 1.2.4.2 rmind error = -EAGAIN; 202 1.2.4.2 rmind goto out; 203 1.2.4.2 rmind } 204 1.2.4.2 rmind idr->idr_temp = NULL; 205 1.2.4.2 rmind 206 1.2.4.2 rmind search = rb_tree_find_node_geq(&idr->idr_tree, &min_id); 207 1.2.4.2 rmind while ((search != NULL) && (search->in_index == want_id)) { 208 1.2.4.2 rmind if (want_id == INT_MAX) { 209 1.2.4.2 rmind error = -ENOSPC; 210 1.2.4.2 rmind goto out; 211 1.2.4.2 rmind } 212 1.2.4.2 rmind search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT); 213 1.2.4.2 rmind want_id++; 214 1.2.4.2 rmind } 215 1.2.4.2 rmind 216 1.2.4.2 rmind node->in_index = want_id; 217 1.2.4.2 rmind node->in_data = data; 218 1.2.4.2 rmind 219 1.2.4.2 rmind collision = rb_tree_insert_node(&idr->idr_tree, node); 220 1.2.4.2 rmind KASSERT(collision == node); 221 1.2.4.2 rmind 222 1.2.4.2 rmind *id = want_id; 223 1.2.4.2 rmind error = 0; 224 1.2.4.2 rmind 225 1.2.4.2 rmind out: mutex_spin_exit(&idr->idr_lock); 226 1.2.4.2 rmind return error; 227 1.2.4.2 rmind } 228 1.2.4.2 rmind 229 1.2.4.2 rmind int 230 1.2.4.2 rmind idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg) 231 1.2.4.2 rmind { 232 1.2.4.2 rmind struct idr_node *node; 233 1.2.4.2 rmind int error = 0; 234 1.2.4.2 rmind 235 1.2.4.2 rmind /* XXX Caller must exclude modifications. */ 236 1.2.4.2 rmind membar_consumer(); 237 1.2.4.2 rmind RB_TREE_FOREACH(node, &idr->idr_tree) { 238 1.2.4.2 rmind error = (*proc)(node->in_index, node->in_data, arg); 239 1.2.4.2 rmind if (error) 240 1.2.4.2 rmind break; 241 1.2.4.2 rmind } 242 1.2.4.2 rmind 243 1.2.4.2 rmind return error; 244 1.2.4.2 rmind } 245
Indexes created Tue Sep 30 11:09:46 GMT 2025