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 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 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 * 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 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 * 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 * 125 radix_tree_deref_slot(void **slot) 126 { 127 128 return atomic_load_consume(slot); 129 } 130 131 void ** 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 ** 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 ** 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 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
Indexes created Sun Sep 21 16:09:51 GMT 2025