1 /* $NetBSD: linux_radixtree.c,v 1.4 2021/12/19 12:07:29 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2021 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <sys/cdefs.h>
30 __KERNEL_RCSID(0, "$NetBSD: linux_radixtree.c,v 1.4 2021/12/19 12:07:29 riastradh Exp $");
31
32 #include <sys/atomic.h>
33 #include <sys/kmem.h>
34 #include <sys/lock.h>
35 #include <sys/radixtree.h>
36
37 #include <linux/gfp.h>
38 #include <linux/radix-tree.h>
39 #include <linux/rcupdate.h>
40 #include <linux/slab.h>
41
42 /* XXX mega-kludgerific */
43 #define __UNVOLANST(p) ((void *)(unsigned long)(const volatile void *)(p))
44
45 struct kludge {
46 uint64_t k_key;
47 void *k_datum;
48 struct rcu_head k_rcu;
49 };
50
51 void
INIT_RADIX_TREE(struct radix_tree_root * root,gfp_t gfp)52 INIT_RADIX_TREE(struct radix_tree_root *root, gfp_t gfp)
53 {
54
55 radix_tree_init_tree(&root->rtr_tree);
56 __cpu_simple_lock_init(&root->rtr_lock);
57 }
58
59 int
radix_tree_insert(struct radix_tree_root * root,unsigned long key,void * datum)60 radix_tree_insert(struct radix_tree_root *root, unsigned long key, void *datum)
61 {
62 struct kludge *kludge;
63 int error;
64
65 /* XXX No way to know whether the caller can sleep or not... */
66 if ((kludge = kzalloc(sizeof(*kludge), GFP_ATOMIC)) == NULL)
67 return -ENOMEM;
68
69 kludge->k_key = key;
70 kludge->k_datum = datum;
71
72 __cpu_simple_lock(&root->rtr_lock);
73 error = radix_tree_insert_node(&root->rtr_tree, key, kludge);
74 __cpu_simple_unlock(&root->rtr_lock);
75
76 /* XXX errno NetBSD->Linux */
77 return -error;
78 }
79
80 void *
radix_tree_delete(struct radix_tree_root * root,unsigned long key)81 radix_tree_delete(struct radix_tree_root *root, unsigned long key)
82 {
83 struct kludge *kludge;
84 void *datum = NULL;
85
86 __cpu_simple_lock(&root->rtr_lock);
87 kludge = radix_tree_remove_node(&root->rtr_tree, key);
88 __cpu_simple_unlock(&root->rtr_lock);
89 if (kludge == NULL)
90 return NULL;
91
92 datum = kludge->k_datum;
93 kfree_rcu(kludge, k_rcu);
94
95 return datum;
96 }
97
98 bool
radix_tree_empty(struct radix_tree_root * root)99 radix_tree_empty(struct radix_tree_root *root)
100 {
101 bool empty;
102
103 __cpu_simple_lock(&root->rtr_lock);
104 empty = radix_tree_empty_tree_p(&root->rtr_tree);
105 __cpu_simple_unlock(&root->rtr_lock);
106
107 return empty;
108 }
109
110 void *
radix_tree_lookup(const struct radix_tree_root * root,unsigned long key)111 radix_tree_lookup(const struct radix_tree_root *root, unsigned long key)
112 {
113 struct kludge *kludge;
114
115 __cpu_simple_lock(__UNVOLANST(&root->rtr_lock));
116 kludge = radix_tree_lookup_node(__UNVOLANST(&root->rtr_tree), key);
117 __cpu_simple_unlock(__UNVOLANST(&root->rtr_lock));
118 if (kludge == NULL)
119 return NULL;
120
121 return kludge->k_datum;
122 }
123
124 void *
radix_tree_deref_slot(void ** slot)125 radix_tree_deref_slot(void **slot)
126 {
127
128 return atomic_load_consume(slot);
129 }
130
131 void **
radix_tree_iter_init(struct radix_tree_iter * I,unsigned long start)132 radix_tree_iter_init(struct radix_tree_iter *I, unsigned long start)
133 {
134
135 I->index = start;
136 I->rti_tree = NULL;
137 return NULL;
138 }
139
140 void **
radix_tree_next_chunk(const struct radix_tree_root * root,struct radix_tree_iter * I,unsigned flags)141 radix_tree_next_chunk(const struct radix_tree_root *root,
142 struct radix_tree_iter *I, unsigned flags)
143 {
144 void *result;
145 struct kludge *kludge;
146 unsigned nresults;
147
148 KASSERT(flags == 0);
149 __cpu_simple_lock(__UNVOLANST(&root->rtr_lock));
150 nresults = radix_tree_gang_lookup_node(__UNVOLANST(&root->rtr_tree),
151 I->index, &result, /*maxresults*/1, /*dense*/false);
152 __cpu_simple_unlock(__UNVOLANST(&root->rtr_lock));
153 if (nresults == 0)
154 return NULL;
155 KASSERT(nresults == 1);
156
157 kludge = result;
158
159 I->index = kludge->k_key;
160 I->rti_tree = root;
161 return &kludge->k_datum;
162 }
163
164 void **
radix_tree_next_slot(void ** slot,struct radix_tree_iter * I,unsigned flags)165 radix_tree_next_slot(void **slot, struct radix_tree_iter *I, unsigned flags)
166 {
167 struct kludge *kludge;
168 void *result;
169 unsigned nresults;
170
171 KASSERT(flags == 0);
172
173 kludge = container_of(slot, struct kludge, k_datum);
174
175 __cpu_simple_lock(__UNVOLANST(&I->rti_tree->rtr_lock));
176 nresults = radix_tree_gang_lookup_node(
177 __UNVOLANST(&I->rti_tree->rtr_tree),
178 kludge->k_key, &result, /*maxresults*/1, /*dense*/true);
179 __cpu_simple_unlock(__UNVOLANST(&I->rti_tree->rtr_lock));
180 if (nresults == 0)
181 return NULL;
182 KASSERT(nresults == 1);
183
184 kludge = result;
185
186 I->index = kludge->k_key;
187 /* XXX Hope the tree hasn't changed! */
188 return &kludge->k_datum;
189 }
190
191 void
radix_tree_iter_delete(struct radix_tree_root * root,struct radix_tree_iter * I,void ** slot)192 radix_tree_iter_delete(struct radix_tree_root *root, struct radix_tree_iter *I,
193 void **slot)
194 {
195 struct kludge *kludge = container_of(slot, struct kludge, k_datum);
196 struct kludge *kludge0 __diagused;
197
198 __cpu_simple_lock(&root->rtr_lock);
199 kludge0 = radix_tree_remove_node(&root->rtr_tree, kludge->k_key);
200 __cpu_simple_unlock(&root->rtr_lock);
201
202 KASSERT(kludge0 == kludge);
203 }
204