1 /* $NetBSD: linux_idr.c,v 1.2 2014/03/18 18:20:43 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.2 2014/03/18 18:20:43 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/err.h> 41 #include <linux/idr.h> 42 43 struct idr_node { 44 rb_node_t in_rb_node; 45 int in_index; 46 void *in_data; 47 }; 48 49 static signed int idr_tree_compare_nodes(void *, const void *, const void *); 50 static signed int idr_tree_compare_key(void *, const void *, const void *); 51 52 static const rb_tree_ops_t idr_rb_ops = { 53 .rbto_compare_nodes = &idr_tree_compare_nodes, 54 .rbto_compare_key = &idr_tree_compare_key, 55 .rbto_node_offset = offsetof(struct idr_node, in_rb_node), 56 .rbto_context = NULL, 57 }; 58 59 static signed int 60 idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb) 61 { 62 const int a = ((const struct idr_node *)na)->in_index; 63 const int b = ((const struct idr_node *)nb)->in_index; 64 65 if (a < b) 66 return -1; 67 else if (b < a) 68 return +1; 69 else 70 return 0; 71 } 72 73 static signed int 74 idr_tree_compare_key(void *ctx __unused, const void *n, const void *key) 75 { 76 const int a = ((const struct idr_node *)n)->in_index; 77 const int b = *(const int *)key; 78 79 if (a < b) 80 return -1; 81 else if (b < a) 82 return +1; 83 else 84 return 0; 85 } 86 87 void 88 idr_init(struct idr *idr) 89 { 90 91 mutex_init(&idr->idr_lock, MUTEX_DEFAULT, IPL_VM); 92 rb_tree_init(&idr->idr_tree, &idr_rb_ops); 93 idr->idr_temp = NULL; 94 } 95 96 void 97 idr_destroy(struct idr *idr) 98 { 99 100 if (idr->idr_temp != NULL) { 101 /* XXX Probably shouldn't happen. */ 102 kmem_free(idr->idr_temp, sizeof(*idr->idr_temp)); 103 idr->idr_temp = NULL; 104 } 105 #if 0 /* XXX No rb_tree_destroy? */ 106 rb_tree_destroy(&idr->idr_tree); 107 #endif 108 mutex_destroy(&idr->idr_lock); 109 } 110 111 void * 112 idr_find(struct idr *idr, int id) 113 { 114 const struct idr_node *node; 115 void *data; 116 117 mutex_spin_enter(&idr->idr_lock); 118 node = rb_tree_find_node(&idr->idr_tree, &id); 119 data = (node == NULL? NULL : node->in_data); 120 mutex_spin_exit(&idr->idr_lock); 121 122 return data; 123 } 124 125 void * 126 idr_replace(struct idr *idr, void *replacement, int id) 127 { 128 struct idr_node *node; 129 void *result; 130 131 mutex_spin_enter(&idr->idr_lock); 132 node = rb_tree_find_node(&idr->idr_tree, &id); 133 if (node == NULL) { 134 result = ERR_PTR(-ENOENT); 135 } else { 136 result = node->in_data; 137 node->in_data = replacement; 138 } 139 mutex_spin_exit(&idr->idr_lock); 140 141 return result; 142 } 143 144 void 145 idr_remove(struct idr *idr, int id) 146 { 147 struct idr_node *node; 148 149 mutex_spin_enter(&idr->idr_lock); 150 node = rb_tree_find_node(&idr->idr_tree, &id); 151 KASSERT(node != NULL); 152 rb_tree_remove_node(&idr->idr_tree, node); 153 mutex_spin_exit(&idr->idr_lock); 154 kmem_free(node, sizeof(*node)); 155 } 156 157 void 158 idr_remove_all(struct idr *idr) 159 { 160 struct idr_node *node; 161 162 mutex_spin_enter(&idr->idr_lock); 163 while ((node = RB_TREE_MIN(&idr->idr_tree)) != NULL) { 164 rb_tree_remove_node(&idr->idr_tree, node); 165 mutex_spin_exit(&idr->idr_lock); 166 kmem_free(node, sizeof(*node)); 167 mutex_spin_enter(&idr->idr_lock); 168 } 169 mutex_spin_exit(&idr->idr_lock); 170 } 171 172 int 173 idr_pre_get(struct idr *idr, int flags __unused /* XXX */) 174 { 175 struct idr_node *temp = kmem_alloc(sizeof(*temp), KM_SLEEP); 176 177 mutex_spin_enter(&idr->idr_lock); 178 if (idr->idr_temp == NULL) { 179 idr->idr_temp = temp; 180 temp = NULL; 181 } 182 mutex_spin_exit(&idr->idr_lock); 183 184 if (temp != NULL) 185 kmem_free(temp, sizeof(*temp)); 186 187 return 1; 188 } 189 190 int 191 idr_get_new_above(struct idr *idr, void *data, int min_id, int *id) 192 { 193 struct idr_node *node, *search, *collision __unused; 194 int want_id = min_id; 195 int error; 196 197 mutex_spin_enter(&idr->idr_lock); 198 199 node = idr->idr_temp; 200 if (node == NULL) { 201 error = -EAGAIN; 202 goto out; 203 } 204 idr->idr_temp = NULL; 205 206 search = rb_tree_find_node_geq(&idr->idr_tree, &min_id); 207 while ((search != NULL) && (search->in_index == want_id)) { 208 if (want_id == INT_MAX) { 209 error = -ENOSPC; 210 goto out; 211 } 212 search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT); 213 want_id++; 214 } 215 216 node->in_index = want_id; 217 node->in_data = data; 218 219 collision = rb_tree_insert_node(&idr->idr_tree, node); 220 KASSERT(collision == node); 221 222 *id = want_id; 223 error = 0; 224 225 out: mutex_spin_exit(&idr->idr_lock); 226 return error; 227 } 228 229 int 230 idr_for_each(struct idr *idr, int (*proc)(int, void *, void *), void *arg) 231 { 232 struct idr_node *node; 233 int error = 0; 234 235 /* XXX Caller must exclude modifications. */ 236 membar_consumer(); 237 RB_TREE_FOREACH(node, &idr->idr_tree) { 238 error = (*proc)(node->in_index, node->in_data, arg); 239 if (error) 240 break; 241 } 242 243 return error; 244 } 245