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