linux_radixtree.c revision 1.2
1 /* $NetBSD: linux_radixtree.c,v 1.2 2021/12/19 11:51:51 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.2 2021/12/19 11:51:51 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_NOWAIT)) == NULL) 67 return -ENOMEM; 68 69 kludge->k_key = key; 70 kludge->k_datum = datum; 71 72 membar_exit(); 73 74 __cpu_simple_lock(&root->rtr_lock); 75 error = radix_tree_insert_node(&root->rtr_tree, key, kludge); 76 __cpu_simple_unlock(&root->rtr_lock); 77 78 /* XXX errno NetBSD->Linux */ 79 return -error; 80 } 81 82 void * 83 radix_tree_delete(struct radix_tree_root *root, unsigned long key) 84 { 85 struct kludge *kludge; 86 void *datum = NULL; 87 88 __cpu_simple_lock(&root->rtr_lock); 89 kludge = radix_tree_remove_node(&root->rtr_tree, key); 90 __cpu_simple_unlock(&root->rtr_lock); 91 if (kludge == NULL) 92 return NULL; 93 94 datum = kludge->k_datum; 95 kfree_rcu(kludge, k_rcu); 96 97 return datum; 98 } 99 100 bool 101 radix_tree_empty(struct radix_tree_root *root) 102 { 103 bool empty; 104 105 __cpu_simple_lock(&root->rtr_lock); 106 empty = radix_tree_empty_tree_p(&root->rtr_tree); 107 __cpu_simple_unlock(&root->rtr_lock); 108 109 return empty; 110 } 111 112 void * 113 radix_tree_lookup(const struct radix_tree_root *root, unsigned long key) 114 { 115 struct kludge *kludge; 116 117 __cpu_simple_lock(__UNVOLANST(&root->rtr_lock)); 118 kludge = radix_tree_lookup_node(__UNVOLANST(&root->rtr_tree), key); 119 __cpu_simple_unlock(__UNVOLANST(&root->rtr_lock)); 120 if (kludge == NULL) 121 return NULL; 122 123 return kludge->k_datum; 124 } 125 126 void * 127 radix_tree_deref_slot(void **slot) 128 { 129 130 return atomic_load_consume(slot); 131 } 132 133 void ** 134 radix_tree_iter_init(struct radix_tree_iter *I, unsigned long start) 135 { 136 137 I->index = start; 138 I->rti_tree = NULL; 139 return NULL; 140 } 141 142 void ** 143 radix_tree_next_chunk(const struct radix_tree_root *root, 144 struct radix_tree_iter *I, unsigned flags) 145 { 146 void *result; 147 struct kludge *kludge; 148 unsigned nresults; 149 150 KASSERT(flags == 0); 151 __cpu_simple_lock(__UNVOLANST(&root->rtr_lock)); 152 nresults = radix_tree_gang_lookup_node(__UNVOLANST(&root->rtr_tree), 153 I->index, &result, /*maxresults*/1, /*dense*/false); 154 __cpu_simple_unlock(__UNVOLANST(&root->rtr_lock)); 155 if (nresults == 0) 156 return NULL; 157 KASSERT(nresults == 1); 158 159 kludge = result; 160 161 I->index = kludge->k_key; 162 I->rti_tree = root; 163 return &kludge->k_datum; 164 } 165 166 void ** 167 radix_tree_next_slot(void **slot, struct radix_tree_iter *I, unsigned flags) 168 { 169 struct kludge *kludge; 170 void *result; 171 unsigned nresults; 172 173 KASSERT(flags == 0); 174 175 kludge = container_of(slot, struct kludge, k_datum); 176 177 __cpu_simple_lock(__UNVOLANST(&I->rti_tree->rtr_lock)); 178 nresults = radix_tree_gang_lookup_node( 179 __UNVOLANST(&I->rti_tree->rtr_tree), 180 kludge->k_key, &result, /*maxresults*/1, /*dense*/true); 181 __cpu_simple_unlock(__UNVOLANST(&I->rti_tree->rtr_lock)); 182 if (nresults == 0) 183 return NULL; 184 KASSERT(nresults == 1); 185 186 kludge = result; 187 188 I->index = kludge->k_key; 189 /* XXX Hope the tree hasn't changed! */ 190 return &kludge->k_datum; 191 } 192 193 void 194 radix_tree_iter_delete(struct radix_tree_root *root, struct radix_tree_iter *I, 195 void **slot) 196 { 197 struct kludge *kludge = container_of(slot, struct kludge, k_datum); 198 struct kludge *kludge0 __diagused; 199 200 __cpu_simple_lock(&root->rtr_lock); 201 kludge0 = radix_tree_remove_node(&root->rtr_tree, kludge->k_key); 202 __cpu_simple_unlock(&root->rtr_lock); 203 204 KASSERT(kludge0 == kludge); 205 } 206
Indexes created Mon Sep 29 21:09:56 GMT 2025