1 /* $NetBSD: linux_xa.c,v 1.2 2021/12/19 12:05:18 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.2 2021/12/19 12:05:18 riastradh Exp $"); 31 32 #include <sys/radixtree.h> 33 34 #include <uvm/uvm_pdaemon.h> 35 36 #include <linux/xarray.h> 37 38 const struct xa_limit xa_limit_32b = { .min = 0, .max = UINT32_MAX }; 39 40 void 41 xa_init_flags(struct xarray *xa, gfp_t gfp) 42 { 43 44 mutex_init(&xa->xa_lock, MUTEX_DEFAULT, IPL_VM); 45 radix_tree_init_tree(&xa->xa_tree); 46 xa->xa_gfp = gfp; 47 } 48 49 void 50 xa_destroy(struct xarray *xa) 51 { 52 53 KASSERT(radix_tree_empty_tree_p(&xa->xa_tree)); 54 radix_tree_fini_tree(&xa->xa_tree); 55 mutex_destroy(&xa->xa_lock); 56 } 57 58 void * 59 xa_load(struct xarray *xa, unsigned long key) 60 { 61 void *datum; 62 63 /* XXX pserialize */ 64 mutex_enter(&xa->xa_lock); 65 datum = radix_tree_lookup_node(&xa->xa_tree, key); 66 mutex_exit(&xa->xa_lock); 67 68 return datum; 69 } 70 71 void * 72 xa_store(struct xarray *xa, unsigned long key, void *datum, gfp_t gfp) 73 { 74 void *collision; 75 int error; 76 77 KASSERT(datum != NULL); 78 KASSERT(((uintptr_t)datum & 0x3) == 0); 79 80 retry: mutex_enter(&xa->xa_lock); 81 collision = radix_tree_lookup_node(&xa->xa_tree, key); 82 error = radix_tree_insert_node(&xa->xa_tree, key, datum); 83 mutex_exit(&xa->xa_lock); 84 if (error) { 85 if (gfp & __GFP_WAIT) { 86 uvm_wait("xa"); 87 goto retry; 88 } 89 /* XXX errno NetBSD->Linux */ 90 return XA_ERROR(-error); 91 } 92 93 return collision; 94 } 95 96 int 97 xa_alloc(struct xarray *xa, uint32_t *idp, void *datum, struct xa_limit limit, 98 gfp_t gfp) 99 { 100 uint32_t key = limit.min; 101 void *collision; 102 int error; 103 104 KASSERTMSG(limit.min < limit.max, "min=%"PRIu32" max=%"PRIu32, 105 limit.min, limit.max); 106 107 retry: mutex_enter(&xa->xa_lock); 108 /* XXX use the radix tree to make this fast */ 109 while ((collision = radix_tree_lookup_node(&xa->xa_tree, key)) 110 != NULL) { 111 if (key++ == limit.max) 112 goto out; 113 } 114 error = radix_tree_insert_node(&xa->xa_tree, key, datum); 115 out: mutex_exit(&xa->xa_lock); 116 117 if (collision) 118 return -EBUSY; 119 if (error) { 120 if (gfp & __GFP_WAIT) { 121 uvm_wait("xa"); 122 goto retry; 123 } 124 /* XXX errno NetBSD->Linux */ 125 return -error; 126 } 127 128 /* Success! */ 129 *idp = key; 130 return 0; 131 } 132 133 void * 134 xa_find(struct xarray *xa, unsigned long *startp, unsigned long max, 135 unsigned tagmask) 136 { 137 uint64_t key = *startp; 138 void *candidate = NULL; 139 140 mutex_enter(&xa->xa_lock); 141 for (; key < max; key++, candidate = NULL) { 142 candidate = radix_tree_lookup_node(&xa->xa_tree, key); 143 if (candidate == NULL) 144 continue; 145 if (tagmask == -1 || 146 radix_tree_get_tag(&xa->xa_tree, key, tagmask)) 147 break; 148 } 149 mutex_exit(&xa->xa_lock); 150 151 if (candidate) 152 *startp = key; 153 return candidate; 154 } 155 156 void * 157 xa_find_after(struct xarray *xa, unsigned long *startp, unsigned long max, 158 unsigned tagmask) 159 { 160 unsigned long start = *startp + 1; 161 void *found; 162 163 if (start == max) 164 return NULL; 165 found = xa_find(xa, &start, max, tagmask); 166 if (found) 167 *startp = start; 168 return found; 169 } 170 171 void * 172 xa_erase(struct xarray *xa, unsigned long key) 173 { 174 void *datum; 175 176 mutex_enter(&xa->xa_lock); 177 datum = radix_tree_remove_node(&xa->xa_tree, key); 178 mutex_exit(&xa->xa_lock); 179 180 return datum; 181 } 182