1 /* $NetBSD: linux_xa.c,v 1.4 2024/05/22 15:59:25 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_xa.c,v 1.4 2024/05/22 15:59:25 riastradh Exp $"); 31 32 /* 33 * This is a lame-o implementation of the Linux xarray data type, which 34 * implements a map from 64-bit integers to pointers. The operations 35 * it supports are designed to be implemented by a radix tree, but 36 * NetBSD's radixtree(9) doesn't quite support them all, and it's a bit 37 * of work to implement them, so this just uses a red/black tree 38 * instead at the cost of some performance in certain types of lookups 39 * (and negative-lookups -- finding a free key). 40 */ 41 42 #include <sys/rbtree.h> 43 44 #include <linux/xarray.h> 45 46 struct node { 47 struct rb_node n_rb; 48 uint64_t n_key; 49 void *n_datum; 50 }; 51 52 static int 53 compare_nodes(void *cookie, const void *va, const void *vb) 54 { 55 const struct node *a = va, *b = vb; 56 57 if (a->n_key < b->n_key) 58 return -1; 59 if (a->n_key > b->n_key) 60 return +1; 61 return 0; 62 } 63 64 static int 65 compare_node_key(void *cookie, const void *vn, const void *vk) 66 { 67 const struct node *n = vn; 68 const uint64_t *k = vk; 69 70 if (n->n_key < *k) 71 return -1; 72 if (n->n_key > *k) 73 return +1; 74 return 0; 75 } 76 77 static const rb_tree_ops_t xa_rb_ops = { 78 .rbto_compare_nodes = compare_nodes, 79 .rbto_compare_key = compare_node_key, 80 .rbto_node_offset = offsetof(struct node, n_rb), 81 }; 82 83 const struct xa_limit xa_limit_32b = { .min = 0, .max = UINT32_MAX }; 84 85 void 86 xa_init_flags(struct xarray *xa, gfp_t gfp) 87 { 88 89 mutex_init(&xa->xa_lock, MUTEX_DEFAULT, IPL_VM); 90 rb_tree_init(&xa->xa_tree, &xa_rb_ops); 91 xa->xa_gfp = gfp; 92 } 93 94 void 95 xa_destroy(struct xarray *xa) 96 { 97 struct node *n; 98 99 /* 100 * Linux allows xa to remain populated on destruction; it is 101 * our job to free any internal node structures. 102 */ 103 while ((n = RB_TREE_MIN(&xa->xa_tree)) != NULL) { 104 rb_tree_remove_node(&xa->xa_tree, n); 105 kmem_free(n, sizeof(*n)); 106 } 107 mutex_destroy(&xa->xa_lock); 108 } 109 110 void * 111 xa_load(struct xarray *xa, unsigned long key) 112 { 113 const uint64_t key64 = key; 114 struct node *n; 115 116 /* XXX pserialize */ 117 mutex_enter(&xa->xa_lock); 118 n = rb_tree_find_node(&xa->xa_tree, &key64); 119 mutex_exit(&xa->xa_lock); 120 121 return n ? n->n_datum : NULL; 122 } 123 124 void * 125 xa_store(struct xarray *xa, unsigned long key, void *datum, gfp_t gfp) 126 { 127 struct node *n, *collision, *recollision; 128 129 KASSERT(datum != NULL); 130 KASSERT(((uintptr_t)datum & 0x3) == 0); 131 132 n = kmem_zalloc(sizeof(*n), gfp & __GFP_WAIT ? KM_SLEEP : KM_NOSLEEP); 133 if (n == NULL) 134 return XA_ERROR(-ENOMEM); 135 n->n_key = key; 136 n->n_datum = datum; 137 138 mutex_enter(&xa->xa_lock); 139 collision = rb_tree_insert_node(&xa->xa_tree, n); 140 if (collision != n) { 141 rb_tree_remove_node(&xa->xa_tree, n); 142 recollision = rb_tree_insert_node(&xa->xa_tree, n); 143 KASSERT(recollision == n); 144 } 145 mutex_exit(&xa->xa_lock); 146 147 if (collision != n) { 148 datum = collision->n_datum; 149 kmem_free(collision, sizeof(*collision)); 150 } 151 return datum; 152 } 153 154 int 155 xa_alloc(struct xarray *xa, uint32_t *idp, void *datum, struct xa_limit limit, 156 gfp_t gfp) 157 { 158 uint64_t key64 = limit.min; 159 struct node *n, *n1, *collision __diagused; 160 int error; 161 162 KASSERTMSG(limit.min < limit.max, "min=%"PRIu32" max=%"PRIu32, 163 limit.min, limit.max); 164 165 n = kmem_zalloc(sizeof(*n), gfp & __GFP_WAIT ? KM_SLEEP : KM_NOSLEEP); 166 if (n == NULL) 167 return -ENOMEM; 168 n->n_datum = datum; 169 170 mutex_enter(&xa->xa_lock); 171 while ((n1 = rb_tree_find_node_geq(&xa->xa_tree, &key64)) != NULL && 172 n1->n_key == key64) { 173 if (key64 == limit.max) { 174 error = -EBUSY; 175 goto out; 176 } 177 KASSERT(key64 < UINT32_MAX); 178 key64++; 179 } 180 /* Found a hole -- insert in it. */ 181 KASSERT(n1 == NULL || n1->n_key > key64); 182 n->n_key = key64; 183 collision = rb_tree_insert_node(&xa->xa_tree, n); 184 KASSERT(collision == n); 185 error = 0; 186 out: mutex_exit(&xa->xa_lock); 187 188 if (error) 189 return error; 190 *idp = key64; 191 return 0; 192 } 193 194 void * 195 xa_find(struct xarray *xa, unsigned long *startp, unsigned long max, 196 unsigned tagmask) 197 { 198 uint64_t key64 = *startp; 199 struct node *n = NULL; 200 201 KASSERT(tagmask == -1); /* not yet supported */ 202 203 mutex_enter(&xa->xa_lock); 204 n = rb_tree_find_node_geq(&xa->xa_tree, &key64); 205 mutex_exit(&xa->xa_lock); 206 207 if (n == NULL || n->n_key > max) 208 return NULL; 209 210 *startp = n->n_key; 211 return n->n_datum; 212 } 213 214 void * 215 xa_find_after(struct xarray *xa, unsigned long *startp, unsigned long max, 216 unsigned tagmask) 217 { 218 unsigned long start = *startp + 1; 219 void *found; 220 221 if (start == max) 222 return NULL; 223 found = xa_find(xa, &start, max, tagmask); 224 if (found) 225 *startp = start; 226 return found; 227 } 228 229 void * 230 xa_erase(struct xarray *xa, unsigned long key) 231 { 232 uint64_t key64 = key; 233 struct node *n; 234 void *datum = NULL; 235 236 mutex_enter(&xa->xa_lock); 237 n = rb_tree_find_node(&xa->xa_tree, &key64); 238 if (n) 239 rb_tree_remove_node(&xa->xa_tree, n); 240 mutex_exit(&xa->xa_lock); 241 242 if (n) { 243 datum = n->n_datum; 244 kmem_free(n, sizeof(*n)); 245 } 246 return datum; 247 } 248